211.字符串置换

描述

给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从1开始。

样例

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

代码

1. O(n)

public class Solution {
    /**
     * @param A a string
     * @param B a string
     * @return a boolean
     */
    public boolean stringPermutation(String A, String B) {
        int[] cnt = new int[1000];
        for (int i = 0; i < A.length(); ++i) {
            cnt[(int)A.charAt(i)] += 1;
        }
        for (int i = 0; i < B.length(); ++i) {
            cnt[(int)B.charAt(i)] -= 1;
        }
        for (int i = 0; i < 1000; ++i) {
            if (cnt[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

2. O(nlogn)

public class Solution {
    /**
     * @param A a string
     * @param B a string
     * @return a boolean
     */
    public boolean Permutation(String A, String B) {
        if (A.length() != B.length()) {
            return false;
        }
        
        char[] listA = A.toCharArray();
        char[] listB = B.toCharArray();
        
        Arrays.sort(listA);   // O(nlogn)
        Arrays.sort(listB);
        
        for (int i = 0; i < listA.length; i++) {
            if (listA[i] != listB[i]) {
                return false;
            }
        }
        return true;
    }
}