Home Computer Science Java Algorithm

171 · Anagrams - LintCode

# Description

Given an array of strings, return all groups of strings that are anagrams.If a string is Anagram,there must be another string with the same letter set but different order in S.

All inputs will be in lower-case

# Example

Example 1:

Input:["lint", "intl", "inlt", "code"]
Output:["lint", "inlt", "intl"]

Example 2:

Input:["ab", "ba", "cd", "dc", "e"]
Output: ["ab", "ba", "cd", "dc"]

# What is Anagram?

  • Two strings are anagram if they can be the same after change the order of characters.

# Solution

  • Anagram 意思是 2 個亂序的 string 的 "排序後的結果" 都會是一樣。

這題用 hashMap 解決： HashMap<String, List<String>>
把排好序的 string 都放到 key 裡，如果 hashmap 裡找到 key = sortedString 的時候，把 original (排序前的 String)，放到 Value List<String> 裡

最後 for loop 一下 hashMap，看一下哪一個 key 的 value List<String> 的長度是大於一，大於一的話代表有 2 個 String，它們排序之後的結果是一樣的。那他們就是 anagram。然後把這個 List 放進 result 裡面。

public class Solution {
	//return: List<String>
	//input: String[]
	public List<String> anagrams(String[] strs) {
		Map<String, List<String>> hm = new HashMap<>();
		// 寫多一個 List 用來存 result
		List<String> res = new ArrayList<>();
		for (String s : strs) {
			// 目標： 排序 s, 把排好序的 s 放到 hm 的 key
			// 步驟： 1）因為 String 是 immutable 所以無法排序，
						// 只能寫成 char []
			char[] charArr = s.toCharArray();
			// 2) 排序
			Arrays.sort(charArr);
			// 3) 存到 String 裡：可以用 new String () or String.valueOf () 都是把它變成 String
			String sortedStr = new String(charArr);
			//String sortedStr = String.valueOf(charArr);
			// 4) 放到 HashMap
			if (!hm.containsKey(sortedStr)){
				// 先 new 一個空的 arrayList
				hm.put(sortedStr, new ArrayList<>());
			}
			// 之後是不管 contain 不 containKey 
			// 都把 original s 放進 hasmap value 的空的 arrayList 裡
				hm.get(sortedStr).add(s);
			}// end of for
			//5）把 hashmap 的 value 中的 List 存到結果裡
			
			for (List<String> list : hm.values()) {
				if (list.size() > 1) {
					res.addAll(list);
				}
			}
			
			// for (String key: hm.keySet()) {
	        //  if (hm.get(key).size() > 1) {
            //    res.addAll(hm.get(key));
            //}
	
			return res;
		}
}
# 另一個寫法
也是用 hashmap, 也要 sorted, 只是不用把 value 存到 List<String>
但和上面的解法相似，HashMap 的 value 直接存下 Integer, 當我 sortedStr 有相同的時候，＋1 ，最後如果這個 hashmap.value 大於 1 時，就存到 res 裡
public class Solution{
	public List<String> anagrams(String[] strs) {
        Map<String, Integer> hm = new HashMap<>();
        List<String> res = new ArrayList<>();
        for (int i = 0; i < strs.length; i++) {
            char[] charArr = strs[i].toCharArray();
            Arrays.sort(charArr);
            String sortedStr = String.valueOf(charArr);
            hm.put(sortedStr, hm.getOrDefault(sortedStr, 0) + 1);
        }
        for (int i = 0; i < strs.length; i++) {
            char[] charArr = strs[i].toCharArray();
            Arrays.sort(charArr);
            String sortedStr = String.valueOf(charArr);
            if (hm.get(sortedStr) > 1) {
                res.add(strs[i]);
            }
        }
        return res;
    }
}