本文共 1223 字，大约阅读时间需要 4 分钟。

题目：对于两个字符串A和B，如果A和B中出现的字符种类相同且每种字符出现的次数相同，则A和B互为变形词，请设计一个高效算法，检查两给定串是否互为变形词。

给定两个字符串A和B及他们的长度，请返回一个bool值，代表他们是否互为变形词。

测试样例："abc",3,"bca",3返回：true

思路：所谓变形词是指这个字符串中出现的元素的种类相同，且每个元素的次数相同，例如都是a出现2次，b出现0次，c出现3次……显然需要统计两个字符串中每个字符的出现次数，显然可以使用hash表来实现，hash表是抽象的数据结构，具体实现时是使用数组来实现的，数组需要定长，因此需要先确定数组的长度，如何确定哈希表数组的长度？首先明确要统计出现次数的是谁？是字符。可能出现的字符范围是什么？是abc……ABC……+—*&￥……12345……【{‘;:?/……等各种字符对应的ascii码是0~127共128个，注意一个常识：标准ascii码使用7位表达128中字符，但是在扩展ascii码中后128个字符用于表达附加字符，因此总是使用8位来表达所有字符，即无论在Java还是c/c++中，字符都有256中可能性。

因此由于字符有0~255共256个值，因此在建立哈希表对应的数组时数组大小为256，然后遍历祖父数组，对每一个字符，使用字符的ascii值计算得到的key作为哈希表数组的下标去哈希表中按照下标找对应的位置，先遍历String1，每个元素+1，然后遍历String2，对每个元素-1，每次-1之后就检验是否<0如果小于0显然表示String2中该字符多余String1中的该字符，于是返回false即可。当最后遍历完String2后再遍历哈希表，看每个位置是否为0，如果不为0则返回false。这个步骤其实可以省略，因为已经保证了长度相等，所以如果String1中某个字符多于String2，那么String2中必然会有字符多于String1，此时必然在-1运算时出现<0的情况而导致提前结束判断。

import java.util.*;public class Transform {    public boolean chkTransform(String A, int lena, String B, int lenb) {        if(A==null || B==null || A.length()!=B.length()){            return false;        }        //将字符串转化为数组进行处理        char[] char1=A.toCharArray();        char[] char2=B.toCharArray();                int[] array=new int[256];                for(int i=0;i

转载地址：http://dtzin.baihongyu.com/