首页 > 其他 > 详细

[Leetcode]-- Anagrams

时间:2014-01-31 14:07:29      阅读:438      评论:0      收藏:0      [点我收藏+]
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
 

思路:map<string, int>记录排序后的字符串以及首次出现的位置。

1. 从strs的第一个元素开始遍历,首先对元素进行排序得到s

2. 在map里查找s

3. 若不存在,将s以及该元素的下标存入map<string ,int>

4. 若存在,首先将第一次出现s时的原始字符串存入结果res,即strs[map[s]],并将map[s]设置为-1(防止下次再存),再将该字符串本身存入结果res

5. 重复以上1-4步,直到遍历结束。

 

 

 
bubuko.com,布布扣
public class Solution {
    public  String sortChars(String s) {
        char[] content = s.toCharArray();
        Arrays.sort(content);
        return new String(content);
    }   

    public ArrayList<String> anagrams(String[] strs) {
        ArrayList<String> res = new ArrayList<String>();
        HashMap<String, LinkedList<String>> hash = new HashMap<String, LinkedList<String>>();
     
        /* Group words by anagram */
        for (String s : strs) {
            String key = sortChars(s); 
            if (!hash.containsKey(key)) {
                hash.put(key, new LinkedList<String>());
            }   
            LinkedList<String> anagrams = hash.get(key);
            anagrams.push(s);
        } 
        for (String key : hash.keySet()) {
            LinkedList<String> list = hash.get(key);
            if (list.size() > 1) {
                for (String t : list) {
                    res.add(t);
                }   
            }
        }   
        return res;
    }
}
bubuko.com,布布扣

 

 

[Leetcode]-- Anagrams

原文:http://www.cnblogs.com/RazerLu/p/3536709.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!