Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Example

Given [“lint”, “intl”, “inlt”, “code”], return [“lint”, “inlt”, “intl”].

Given [“ab”, “ba”, “cd”, “dc”, “e”], return [“ab”, “ba”, “cd”, “dc”].

Note

All inputs will be in lower-case

Solution

sorted_string: A list of sorted strings matching the input strs For example:

strs: = {"ab", "ba", "e"}
sorted_string: = {"ab", "ab", "e"}

hash_map : <sorted_string[i], NumofAppearance(sorted_string[i])> maintain how many times does each sorted string appear.
1. Sort each string from strs and put it into sorted_string
2. Use the hash map to record how many times does sorted_string[i] appear.
3. Chose the string which appear more than 2 times. Put it into result string

Anagrams (Anagrams.py) download

class Solution:
    # @param strs: A list of strings
    # @return: A list of strings
    def anagrams(self, strs):
        # write your code here
        # hash_map: hash map indexed by sorted_str
        # sorted_str: a list of strings matching strs
        # return_strs: a list of return strings
        hash_map = dict()
        sorted_str = []
        for unsorted_str in strs:
            tmp_str = ''.join(sorted(unsorted_str))
            sorted_str.append(tmp_str)
            if tmp_str in hash_map:
                hash_map[tmp_str] += 1
            else:
                hash_map[tmp_str] = 1

        return_strs = [strs[i] for i in range(len(strs)) if hash_map[sorted_str[i]] > 1]
        return return_strs