LintCode 乱序字符串题目分析代码

题目

给出一个字符串数组S,找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串,那么他存在一个字母集合相同,但顺序不同的字符串也在S中。

注意事项

所有的字符串都只包含小写字母

样例 对于字符串数组 ["lint","intl","inlt","code"]

返回 ["lint","inlt","intl"]

分析

通过hash的思想,我们就是要计算出一个字符串出现的字符以及每个字符出现的次数,如果一样,则说明,两个字符就是Anagram。我们可以写一个hash函数,将每个字符串转换成字母加数字的形式。 比如,lintt,的hash就是i1l1n1t2,这样就可以判断两个字符是不是Anagram。 再利用hashmap的特性,我们很容易实现这个算法,具体看代码

代码

public class Solution {
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
  public ArrayList<String> anagrams(String[] strs) {
        HashMap<String,ArrayList<String>> hash = new HashMap<>();
        
        for(String str : strs) {
            // create unique label for each string
            String key = generalLabel(str);
            // map the label to a list of anagrams
            if(!hash.containsKey(key)) {
                ArrayList<String> temp = new ArrayList<>(); 
                hash.put(key, temp);
                temp.add(str);
            }
            else {
                hash.get(key).add(str);
            }
        }
        
        ArrayList<String> res = new ArrayList<>();
        
        for(ArrayList<String> anagram : hash.values()) {
             // ignore strings without anagrams
            if(anagram.size() > 1)
                res.addAll(anagram);
        }
        
        return res;
    }
    /*  
     * create a unique label for a string  
     * "cat", "atc" => a1c1t1  
     */  
    private String generalLabel(String str) {
        int[] hash = new int[26];
        for(int i=0;i<str.length();i++) {
            int idx = (int)(str.charAt(i)-'a');
            hash[idx]++;
        }
        
        StringBuilder sb = new StringBuilder();
        
        for(int i=0;i<26;i++) {
            if(hash[i] == 0)
                continue;
            char c = (char)('a' + i);
            sb.append(c);
            sb.append(hash[i]);
        }
        return sb.toString();
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

Top 6 常见问题关于Java中的Map1 将Map转换成一个List2 遍历map中的键值对3 根据Map的key值排序4 根据Map的value值排序5 初始化一个静态的不可变的Map6 Has

我们都知道Map是一种键-值对的数据结构,每个键都是唯一的!本文讨论了关于Java中Map使用的最常见的8个问题。为了叙述的简单,所有的例子都会使用泛型。并且本...

813
来自专栏黑泽君的专栏

java基础学习_集合类04_Map接口、Collections工具类_day18总结

============================================================================= ==...

801
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-17(01)总结,TreeSet,LinkHashSet

(3)TreeSet集合 A:底层数据结构是红黑树(是一个自平衡的二叉树) B:保证元素的排序方式 a:自然排序(元素具备比较性) 让元素所属的类实现C...

3326
来自专栏武培轩的专栏

剑指Offer-和为S的两个数字

题目描述 输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。 输出描述: 对应每...

3264
来自专栏海说

16、Collection接口及其子接口Set和List(常用类LinkedList,ArrayList,Vector和Stack)

16、Collection接口 Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(...

2260
来自专栏吾爱乐享

java之学习去除ArrayList中重复自定义对象元素

1686
来自专栏Java进阶之路

一道有趣的Map迭代题

2080
来自专栏浪淘沙

java学习day07 常用API

2018.6.11 1.object 所有类的父类 toString 打印对象的地址值 hashCode 对象的存储位置的算法 ...

1423
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题37两个链表的第一个公共结点

本题的详细解析均在代码注释中: import java.util.Stack; /** * 题目:输入两个链表,找出他们的第一个公共结点 * @autho...

3165
来自专栏desperate633

排列类算法问题大总结全排列分析带重复元素的全排列代码下一个排列分析上一个排列分析第k个排列分析排列序号分析排列序号II分析

[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

981

扫码关注云+社区

领取腾讯云代金券