Anagrams

Anagrams (leetcodelintcode)

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

Notice
All inputs will be in lower-case

Example
Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].
Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].

What is Anagram?
- Two strings are anagram if they can be the same after change the order of characters.

解题思路

一、HashMap

• 对每个字符串 string 进行排序得到 string' 。
• 然后在 HashMap 中存储 string' < — > List < string > 。
  • 没有对应排序字符串 string' ，新建 List ，存储当前配对 。
  • 存在对应 string' ，将原始 string 加入对应链表。
• 最后输出所有满足条件的 anagrams 。

算法复杂度

• 时间复杂度：在 for 循环中有字符串排序，所以是 N * L * O(logL) ，其中 N 是字符串数组长度， L 是最长字符串的长度。

易错点

1. Java 中对字符串 String 排序，需要先转化为 char 类型数组，用 Arrays.sort() 排序后再转成字符串。

Java 实现

public
class
Solution
{

/**
     * 
@param
 strs: A list of strings
     * 
@return
: A list of strings
     */
public
 List
<
String
>
anagrams
(String[] strs)
{
        List
<
String
>
 results = 
new
 ArrayList
<
String
>
();

if
 (strs == 
null
) {

return
 results;
        }

        HashMap
<
String, List
<
String
>
>
 map = 
new
 HashMap
<
String, List
<
String
>
>
();

for
 (
int
 i = 
0
; i 
<
 strs.length; i++) {
            String s = strs[i];

char
[] chars = s.toCharArray();

            Arrays.sort(chars);
            String sSort = 
new
 String(chars);


if
 (map.containsKey(sSort)) {
                map.get(sSort).add(s);
            } 
else
 {
                List
<
String
>
 list = 
new
 ArrayList
<
String
>
();
                list.add(s);
                map.put(sSort, list);
            }
        }


for
 (List
<
String
>
 list : map.values()) {

if
 (list.size() 
>
1
) {
                result.addAll(list);
            }
        }


return
 results;

    }
}

二、HashMap 2

思路同方法一类似，只是对string排序进行了优化，改为了对每个string求哈希值。

算法复杂度

• 时间复杂度：求哈希值函数的复杂度是 O(L) ， L 为最长字符串的长度。所以算法复杂度优化为 N * O(L) ， N 为字符串数组长度。

Java 实现

public
class
Solution
{

/**
     * 
@param
 strs: A list of strings
     * 
@return
: A list of strings
     */
public
 List
<
String
>
anagrams
(String[] strs)
{
        List
<
String
>
 results = 
new
 ArrayList
<
String
>
();

if
 (strs == 
null
) {

return
 results;
        }

        HashMap
<
Integer, ArrayList
<
String
>
>
 map = 
new
 HashMap
<
Integer, ArrayList
<
String
>
>
();


for
 (String str : strs) {

int
[] count = 
new
int
[
26
];

for
 (
int
 i = 
0
; i 
<
 str.length(); i++) {
                count[str.charAt(i) - 
'a'
]++;
            }


int
 hash = getHash(count);

if
 (!map.containsKey(hash)) {
                map.put(hash, 
new
 ArrayList
<
String
>
());
            }
            map.get(hash).add(str);
        }


for
 (ArrayList
<
String
>
 tmp : map.values()) {

if
 (tmp.size() 
>
1
) {
                results.addAll(tmp);
            }
        }


return
 results;
    }


private
int
getHash
(
int
[] count)
{

int
 hash = 
0
;

int
 a = 
378551
;

int
 b = 
63689
;

for
 (
int
 num : count) {
            hash = hash * a + num;
            a = a * b;
        }

return
 hash;
    }
}

参考

1. Anagrams.java | shawnfan/LintCode
2. Anagrams | 九章算法