LeetCode 2. Add Two Numbers, 49. Group Anagrams
This post was migrated from Tistory. You can find the original here.
Problem
Approach
This problem is about solving the algorithm within the constraints of the singly-linked list structure given in the problem statement.
At first, I converted things to a string and reversed it to flip the order,
but you can also reverse it through addition, like val*1 + val*10 + val*100. (I used to do it this way a lot back in my C classes.)
There are two ways to build the linked list you need to return.
Say you need a linked list like 2 -> 3 -> 1 -> 4.
Build it from the front (starting at 2) = recursion
Build it from the back (starting at 4)
Recursion was the approach that came to my mind first.
However, since the final result ends up reversed given the flow of the problem, building from the front requires an extra reverse step.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Recursive approach
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
a1_val, a2_val = 0, 0
num = 1
while 1:
a1_val += l1.val * num
num *= 10
if not l1.next:
break
l1 = l1.next
num = 1
while 1:
a2_val += l2.val * num
num *= 10
if not l2.next:
break
l2 = l2.next
a3 = list(str(a1_val + a2_val))
a3.reverse()
return self.linked(a3, 0)
def linked(self, arr, idx):
if idx == len(arr):
return None
else:
return ListNode(arr[idx], self.linked(arr, idx+1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Build-from-the-back approach
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
a1_val, a2_val = 0, 0
num = 1
while 1:
a1_val += l1.val * num
num *= 10
if not l1.next:
break
l1 = l1.next
num = 1
while 1:
a2_val += l2.val * num
num *= 10
if not l2.next:
break
l2 = l2.next
a3 = list(str(a1_val + a2_val))
result = None
for i in range(len(a3)):
if i==0:
result = ListNode(a3[i])
prev = result
else:
result = ListNode(a3[i], prev)
prev = result
return result
Problem
Approach
At first, sorting on every iteration seemed boring, so I took a different approach. As it turns out, sorting is actually the faster option.
I tried building a hash value for each string from the sum of the squares of the ASCII codes of its characters.
I figured that just summing the ASCII codes plain would produce collisions, so I mixed in the squares too, but collisions still showed up.
So, when a hash value has already appeared before and set(string) differs, I run it through a condition and change the value.
Because of this, I have to remember the hash values and set(string) that have appeared so far in a dictionary, and depending on the case, there can be an inefficient number of iterations.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Per-string hash value approach
# ex) gethash(abc)=32123, gethash(bac)=32123
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
hashmap = {}
history = {}
for i in strs:
locate = self.gethash(i, history)
if hashmap.get(locate):
hashmap[locate].append(i)
else:
hashmap[locate] = [i]
return list(hashmap.values())
def gethash(self, s, history):
result = 0
for i in s:
result += ord(i)**2 + ord(i)
prevent = history.get(result)
if prevent and set(prevent) != set(s):
result += 1
while True:
result += 1
h = history.get(result)
if not h or set(h) == set(s):
break
history[result] = set(s)
return result
1
2
3
4
5
6
7
8
9
10
11
12
13
# Sort-based approach
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
hashmap = {}
for i in strs:
k = list(i)
k.sort()
k = "".join(k)
if hashmap.get(k):
hashmap[k].append(i)
else:
hashmap[k] = [i]
return list(hashmap.values())