LintCode-211StringPermutation


题目:

给定两个字符串,请设计一个方法来判定其中一个字符串是否为另一个字符串的置换。 置换的意思是,通过改变顺序可以使得两个字符串相等。

样例:

"abc" 为 "cba" 的置换。 "aabc" 不是 "abcc" 的置换。

思路1

使用Hash表,时空复杂度为O(n)

代码如下:

public class J211_StringPermutation {  
    public boolean run(){
        String s1,s2;

        Scanner scan = new Scanner(System.in);
        s1 = scan.next();
        s2 = scan.next();


        if (s1.length() != s2.length()){
            return false;
        }else{

            int[] s1_asc = new int[127];
            int[] s2_asc = new int[127];

            for (int i = 0 ; i<s1.length(); ++i){
                s1_asc[s1.charAt(i)] ++;
                s2_asc[s2.charAt(i)] ++;
            }

            for (int i = 0 ; i < s1.length() ; ++i){
                if (s1_asc[i] != s2_asc[i]){
                    return false;
                }
            }

        }
        return true;
    }
}

思路2

将两个字符串进行排列,然后比较排列后的字符串是否相等。

要点1:==只能比较基本数据类型,string的比较需要使用equals

要点2:注意char[]与string之间的互相转换

代码如下:

 /**
     * O(lgn) 将两个字符串排序,然后比较是否相同
     * @return 是否是置换字符串
     */
    public boolean run2(){

        String A,B;

        Scanner scan = new Scanner(System.in);
        A = scan.next();
        B = scan.next();

        if (A.length() != B.length()){
            return false;
        }

        char[] ca = A.toCharArray();
        char[] cb = B.toCharArray();

        Arrays.sort(ca);
        Arrays.sort(cb);

        A = String.valueOf(ca);
        B = String.valueOf(cb);

//        System.out.println(A);
//        System.out.println(B);

        if (!A.equals(B)){
            return false;
        }

        return true;
    }

分享博文


评论博文


Last one :   LintCode-51PreviousPermutation

Next article :   ML-AlphaGo Zero原理浅析