【题目】
给定两个字符串 str1 和 str2，如果 str1 和 str2 中出现的字符种类一样且每种字符出现的次数也一样，那么 str1 和 str2 互为变形词。请实现函数判断两个字符串是否互为变形词。
【举例】
str1="123", str2="231", 返回 true
str1="123", str2="2331", 返回 false
【要求】
如果字符的种类为 M，str1 和 str2 的长度为 N，那么该方法的时间复杂度为 O(N), 空间复杂度为 O(M)
【难度】
一星
【解答】
如果字符串 str1 和 str2 长度不同，直接返回 false。如果长度相同，假设出现字符的编码值在 0~255 之间，那么闲申请一个长度为 256 的整型数组 map, map[a] = b 代表字符编码为 a 的字符出现了 b 次，初始时 map[0...255] 的值都是 0。然后遍历字符串 str1,统计每种字符出现的数量，比如遍历到字符 'a', 其编码值为 97, 则令 map[97]++。这样 map 就成了 str1 中每种字符的词频统计表。然后遍历字符串 str2, 每遍历到一个字符都在 map 中把词频减下来，比如遍历到字符 'a', 其编码值为 97，则令 map[97]--，如果减少之后的值小于 0,直接返回false, 如果遍历完 str2, map 中的值也没出现负值，则返回true。如果字符的类型很多, 可以用哈希表替代长度为 256 的整型数组。
具体实现请参考下面代码中的 isDeformation 方法。
1 import java.util.Map; 2 import java.util.HashMap; 3 4 public class Main { 5 6 public static void main(String[] args) { 7 System.out.println(new Main().isDeformation("123", "231"));//true 8 System.out.println(new Main().isDeformation("123", "2331"));//false 9 System.out.println(new Main().isDeformation("123", "221"));//false10 11 System.out.println(new Main().isDeformation2("123", "231"));//true12 System.out.println(new Main().isDeformation2("123", "2331"));//false13 System.out.println(new Main().isDeformation2("123", "221"));//false14 }15 16 public boolean isDeformation(String str1, String str2){17 if(str1 == null || str2 == null || str1.length()!= str2.length()) return false;18 char[] chs1 = str1.toCharArray(), chs2 = str2.toCharArray();19 int[] map = new int[256];20 for(char ch : chs1){21 map[ch]++;22 }23 for(char ch : chs2){24 if(--map[ch] < 0){25 return false;26 }27 }28 return true;29 }30 31 //如果字符的类型很多, 可以用哈希表替代长度为 256 的整型数组32 public boolean isDeformation2(String str1, String str2){33 if(str1 == null || str2 == null || str1.length()!= str2.length()) return false;34 char[] chs1 = str1.toCharArray(), chs2 = str2.toCharArray();35 Map map = new HashMap ();36 for(char ch : chs1){37 if(map.containsKey(ch)){38 int count = map.get(ch);39 map.put(ch, ++count);40 }else{41 map.put(ch, 1);42 }43 }44 for(char ch : chs2){45 if(!map.containsKey(ch)) return false;46 int count = map.get(ch);47 if(--count < 0) return false;48 map.put(ch, count);49 }50 return true;51 }52 53 }