一个常见的算法题目

/**
* 假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配,
* 比如:abcda和adabc,由于出现的字符个数都是相同,
* 只是顺序不同,所以这两个字符串是匹配的,
* 要求高效.
*/
public class CompareString{
    public static void main(String args[]){
       System.out.println(compare(args[0],args[1]));
    }
    public static char[] copyNew(char[] src,int exclude){
        char[] n = new char[src.length-1];
        int i=0,j=0;
        for(; i<src.length ;i++){
            if(i != exclude){
                n[j] = src[i];
                j++;
            }
        }
        return n;
    }

    public static boolean compare(String str1,String str2){
        char [] char1 = str1.toCharArray();
        char [] char2 = str2.toCharArray();
        if(char1.length != char2.length ){
            return false;
        }
        char[] _char = new char[char1.length];
        char[] tmp = char2;
        for(int i=0;i< char1.length;i++){
            int j=0;
            for(;j< tmp.length;j++){
                if(char1[i] == tmp[j]){
                   tmp = copyNew(tmp,j);
                   //处理下一个
                   break;
                }
                if(j == tmp.length-1){
                  //在第二个数组没找到相同的
                   return false;
                }
            }
        }
        return true;
    }
}
//=================
这道题有一个陷阱,上面这个解法显然不是高效的,我从编程之美中学到一个思路,
就是通过比较字符串对应的ASCII码的和,来判断

public class CompareString{
    public static void main(String args[]){
       System.out.println(compare(args[0],args[1]));
    }
    public static boolean compare(String str1,String str2){
        char [] char1 = str1.toCharArray();
        char [] char2 = str2.toCharArray();
        if(char1.length != char2.length ){
            return false;
        }
        int sum1=0,sum2=0;
        for(char c:char1){
            sum1 = sum1+(int)c;
        }
        for(char c:char2){
            sum2 = sum2+(int)c;
        }
        if(sum1 == sum2){
            return true;
        }
        return false;
    }
}
</pre>
This entry was posted in Program. Bookmark the permalink.