问题
给定两个字符串，如何判断一个是否为另一个的全排列字符串。
全排列 - 通过改变顺序可以使得两个字符串相等。
假设给定字符串 ‘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;
}
更多
获取更多内容请关注微信公众号豆志昂扬:
- 直接添加公众号豆志昂扬；
- 微信扫描下图二维码；
