LeetCode 17 - Valid Anagram

Valid Anagram

Given two strings s and t , write a function to determine if t is an anagram of s.

1
2
3
4
5
6
7
8
9
10
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def getCharIndex(self, char):
return ord(char) - 97
def isAnagram(self, s, t):
chars = [0] * 26
if len(s) != len(t):
return False
for i in xrange(len(s)):
characterSIndex = self.getCharIndex(s[i])
chars[characterSIndex] += 1
characterTIndex = self.getCharIndex(t[i])
chars[characterTIndex] -= 1
for i in xrange(len(chars)):
if chars[i] != 0:
return False
return True

Given the assumptions that the strings will only be lowercase, you can get the index of each character in the array by subtracting the ord(char) by 97 which is the ordinal value of a. Then you loop through one of the strings, add and then subtract each index. Finally you loop through the 26 length char array and as soon as you encounter an index that isn’t 0 then the strings aren’t anagrams.

Time complexity O(n)
Space complexity O(1) because 26 char array doesn’t grow with size.

For unicode follow-up, you can use a hash table.