[算法]字符串之变形词问题

 

一、判断两个字符串是否互为变形词：

题目：

如果两个字符串中字符的种类相同并且每种字符出现的次数也相同，那么这两个字符串互为变形词。

解法一：

该方法适合只包含8位字符集的字符串，不适合包含中文的字符串比较。

思路：首先判断两个字符串的长度，如不同直接返回false;如果相同，则创建一个长度为256的整型数组，map[a]=b表示字符编码为a的字符出现了b次，遍历第一个字符串时，将对应字符对应的值加一，遍历另一个字符串时，将对应字符的值减一，（当然这两个过程既可以同时进行，也可以分先后进行），最后查看整型数组的每一项的值是否都为0，只要有一个不为零，则返回false，（或者判断是否有字符对应的值大于零，因为首先判断了两个字符串的长度是否相同，如果相同，而且两个字符串又不互为变形词，那么一定会出现第二个字符串的至少一种字符的个数大于第一个，此时该字符对应的值遍历后小于0。

      public static boolean isAnagram(String str1, String str2) {
        if (str2 == null || str1 == null || str1.length() != str2.length()) {
            return false;
        }
        char[] c1 = str1.toCharArray();
        char[] c2 = str2.toCharArray();
        int[] map = new int[256];
        //形式一：
        for (int i = 0; i < c1.length; i++) {
            map[c1[i]]++;
        }
        for (int i = 0; i < c2.length; i++) {
            if (map[c2[i]]-- == 0)
                return false;
        }
        /* 形式二：
        for (int i = 0; i < c1.length; i++) {
            map[c1[i]]++;
            map[c2[i]]--;
        }
        for (int i = 0; i < map.length; i++) {
            if (map[i] != 0)
            return false;
        }*/
        return true;
    }

解法二：

借助于Arrays工具类：

首先排序，然后查看是否相等，在效率上不如解法一。

public boolean isAnagram(String s1, String s2) {
            if (s1 == null || s2 == null || s1.length() != s2.length()) {
                return false;
            }
            char[] ch1 = s1.toCharArray();
            char[] ch2 = s2.toCharArray();
            Arrays.sort(ch1);
            Arrays.sort(ch2);
            return Arrays.equals(ch1, ch2);
        }

解法三：

借助HashMap，原理与解法一基本相同，但是通用于Unicode字符。

public static  boolean isAnagram(String s1,String s2){
        if (s1==null||s2==null||s1.length()!=s2.length())
            return  false;
        char[] c1=s1.toCharArray();
        char[] c2=s2.toCharArray();
        Map<Character, Integer> map=new HashMap<Character, Integer>();
        for (int i=0;i<c1.length;i++){
            if (map.get(c1[i])==null)
                map.put(c1[i],1);
            else
                map.put(c1[i],map.get(c1[i])+1);
            if (map.get(c2[i])==null||map.get(c2[i])==0)
                return false;
            else
                map.put(c2[i],map.get(c2[i])-1);
        }
        return true;
    }

 

 

二、给出一个一组字符串，返回所有是变形词的组

解法一：

如果两个字符串互为变形词，那么排序后的字符串相同（一中的解法二），以排序后的字符串为key，以每一组变形词组成的list为value

public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map=new HashMap<>();
        for(String s:strs){
            char[] c=s.toCharArray();
            Arrays.sort(c);
            String key=new String(c);
            if(map.get(key)==null)
            map.put(key,new ArrayList<String>(Arrays.asList(s)));
            else
           map.get(key).add(s);
        }
        for (List<String> val : map.values())
            Collections.sort(val);
        return new ArrayList<List<String>>(map.values());
    }