字符串：字符串中的变位词

2023-10-30 08:48

文章标签 字符串变位

本文主要是介绍字符串：字符串中的变位词，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

题目
- 案例
暴力枚举法
哈希表+双指针解法
- 代码
总结

题目

输入字符串s1和s2, 判断s2中是否包含字符串s1的某个变位词。前置条件：字符串都是小写字母，这意味着其最大长度为26.

案例

输入：s1=“ac”; s2=“dgcaf”;
输出：true
s2中包含s1的变位词，其中s2的子字符串"ca"是"ac"的变位词。

暴力枚举法

首先我们需要理解什么是变位词。字符串s1的变位词一定是字母出现的次数相同、字符长度相同，唯一不同的是他们的顺序不同。根据这个特点，求s1的变位词，也就是求字符串s1所包含的字符有多少中排列方式。

用暴力枚举法，时间复杂度达到了n的阶层。步骤是：首先计算s1的字符串有多少种排列；然后判断每个排列是不是判断字符串s2的子字符串。

哈希表+双指针解法

我们可以用哈希表，统计字符串中字母出现的次数。哈希表的键是字母，value是字母出现的次数。

首先，我们统计s1中字母出现的次数。

int[] counts = new int[26]; //因为哈希表长度固定，这里用数组简化。
for (int i=0; i < s1.length(); i++) {counts[s1.chatAt(i - 'a')]++;counts[s2.chatAt(i-'a')]--;
}

然后，我们判断s2的子字符串中是否包含s1的变位词。这里可以用双指针来得到一个子字符串，其长度和s1的长度相同。双指针每次向右移动一位，s2每新增一位，counts数组就在新增的那一位加一，而最左边那一位是s2删除的一位，counts数组需要在对最左这一个位减1。

for(int i = s1.length(); i < s2.length(); i++) {counts[s2.chatAt(i)- 'a']++; // i 表示第二个指针counts[s2.chatAt(i - s1.length()) - 'a']--; // i - s1.length 表示第一个指针。指针区间是s1的变位词的长度
}

当counts数组的内容都是数字0时，说明找到了s1的变位词。

private boolean isAllZero(int[] counts) {for(int count: counts) {if(count != 0) {return false;}}return true;
}

代码

    public boolean checkInclusion(String s1, String s2) {if (s2.length() < s1.length()) {return false;}int[] counts = new int[26];for (int i = 0; i < s1.length(); i++) {counts[s1.charAt(i - 'a')]++;counts[s2.charAt(i - 'a')]--;}if (isAllZero(counts)) return true;for (int i = s1.length(); i < s2.length(); i++) {counts[s2.charAt(i) - 'a']--; // i 表示第二个指针counts[s2.charAt(i - s1.length()) - 'a']++; // 从子字符串删除一个元素。if (isAllZero(counts)) return true;}return false;}private boolean isAllZero(int[] counts) {for (int count : counts) {if (count != 0) {return false;}}return true;}