经典面试题34 - 字符串的全排列

问题

给定两个字符串，如何判断一个是否为另一个的全排列字符串。

全排列 - 通过改变顺序可以使得两个字符串相等。

假设给定字符串 ‘bacda’和‘aabcd’， 其就是全排列字符串。

解答

如果不考虑运行效率，可以分别对两个字符串进行排序，排序后的两个字符串如果完全相等则返回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));
    }   

上面思路的时间复杂度大于O(n)的，我们可以参考经典面试题33 - 字符串有无重复字符中的思路，

我们定义一个数组，其长度就是字符集的长度（字符串长度不相等不可能是全排列关系），其中预先填充所有值为0。 首先遍历一遍s1中的字符，将其对应位置增1，然后再遍历s2，将其对应位置减1。

如果在遍历s2的时候，发现数组中出现负数，则说明s2和s1不是全排列关系，返回false，若s2遍历能够完成，返回true。

Java代码如下：

 public static boolean permutation(String s, String t) {
        if (s.length() != t.length()) return false; 
        
        int[] letters = new int[128]; // 假设是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; 
    }

更多

经典面试100题 - 持续更新中

获取更多内容请关注微信公众号豆志昂扬:

• 直接添加公众号豆志昂扬；
• 微信扫描下图二维码；