[Python][leetcode 451. Sort Characters By Frequency] Direct Address Table _ characters

📕 Problem

https://leetcode.com/problems/sort-characters-by-frequency/description/

- LeetCode

 

---

💡 My Solution

This problem is about DAT (Direct Address Table). Because This concept is useful to sort list in O(n), I wanted to practice DAT. It is also called as Bucket Sort Problems. There are two main types, one is using numbers for bucket, the other is using characters. Especially this problem is using characters. So I had to use ord() ans chr() functions to make strings into numbers. The concenpt is same, but this functions are used in Python. Becuase ord('A') = 65, ord('Z')  = 90, ord('a') = 97 and ord('z') = 122. I made a bucket size as 200 which is big enough to contain all of the character indexes.

class Solution:
    def frequencySort(self, s: str) -> str:
        lst = list(s)
        bucket = [0]*200
        for i in range(len(s)):
            temp = ord(lst[i])
            bucket[temp] += 1
        temp = []
        for j in range(len(bucket)):
            if bucket[j] > 0:
                for k in range(bucket[j]):
                    temp.append([bucket[j],chr(j)])
        temp.sort(reverse = -1)
        ans = []
        for i in range(len(temp)):
            ans.append(temp[i][1])
        print(ans)
        ans2 = "".join(ans)
        print(ans2)
        return ans2

 

---

✔️  TIL (Today I Learned)

When I want to solve these types of problem, I need to use the keyword "Bucket Sort". Because all of my colleagues called this as DAT in my class, I didn't know that at first. 

---

💻 Final Answer