問題

給定兩個(gè)字符串，如何判斷一個(gè)是否為另一個(gè)的全排列字符串。

全排列 - 通過改變順序可以使得兩個(gè)字符串相等。

假設(shè)給定字符串 ‘bacda’和‘a(chǎn)abcd’， 其就是全排列字符串。

解答

如果不考慮運(yùn)行效率，可以分別對(duì)兩個(gè)字符串進(jìn)行排序，排序后的兩個(gè)字符串如果完全相等則返回true，反之返回false。

Java代碼如下：

     public String sort(String s) {
        char[] content = s.toCharArray();
        java.util.Arrays.sort(content);
        return new String(content);
    }
    
    public boolean permutation(String s, String t) {
        return sort(s).equals(sort(t));
    }   

上面思路的時(shí)間復(fù)雜度大于O(n)的，我們可以參考經(jīng)典面試題33 - 字符串有無重復(fù)字符中的思路，

我們定義一個(gè)數(shù)組，其長度就是字符集的長度（字符串長度不相等不可能是全排列關(guān)系），其中預(yù)先填充所有值為0。 首先遍歷一遍s1中的字符，將其對(duì)應(yīng)位置增1，然后再遍歷s2，將其對(duì)應(yīng)位置減1。

如果在遍歷s2的時(shí)候，發(fā)現(xiàn)數(shù)組中出現(xiàn)負(fù)數(shù)，則說明s2和s1不是全排列關(guān)系，返回false，若s2遍歷能夠完成，返回true。

Java代碼如下：

 public static boolean permutation(String s, String t) {
        if (s.length() != t.length()) return false; 
        
        int[] letters = new int[128]; // 假設(shè)是ASCII編碼集
        for (int i = 0; i < s.length(); i++) {
            letters[s.charAt(i)]++;
        }
          
        for (int i = 0; i < t.length(); i++) {
            letters[t.charAt(i)]--;
            if (letters[t.charAt(i)] < 0) {
                return false;
            }
        }
          
        return true; 
    }

更多

經(jīng)典面試100題 - 持續(xù)更新中

獲取更多內(nèi)容請(qǐng)關(guān)注微信公眾號(hào)豆志昂揚(yáng):

• 直接添加公眾號(hào)豆志昂揚(yáng)；
• 微信掃描下圖二維碼；