当前位置：首页 > ai >正文

【算法专题训练】11、字符串中的变位词

ai 2025/8/12 14:50:25

1、字符串基础知识

字符串是由任意长度的字符组成的字符数组，用于表示文本内容，使用string类型来表示
string类型表达的字符串是无法改变内容的，只能进行读操作，如果要进行写操作，那么会新创建一个字符串对象。原来的字符串保持不变。
若要改变原来的字符串内容，Java中可使用StringBuilder实例。

2、LCR 014. 字符串的排列

题目信息：

https://leetcode.cn/problems/MPnaiL/description/

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。示例 1：
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例 2：
输入: s1= "ab" s2 = "eidboaoo"
输出: False

变位词：

变位词就是单词的长度和字母个数都相同的字符串
例如：字符串abc的变位词有：bac，acb等一共6个，变位词的个数是字符串长度的阶乘

解题思路：双指针哈希表解法

此题只需要记录短字符串中字母出现的个数，然后再通过双指针遍历长字符串的子字符数组，判断区域范围内出现的字母和个数是否相等
可以使用哈希表保存字符串中每个字符串出现的次数，由于字母一共有26个，考虑使用int[]数组结构作为哈希表
刚开始int[]数组中所有元素都为0；遍历短字符串s1的所有字符，记录字母出现的次数，记录的哈希表作为后面比对的基准值
接着遍历长字符串s2的字符，长字符串的比对采用双指针定位遍历区域，控制比对的区域与短字符串相同的长度，并将双指针往右移动，在移动过程中记录子字符串子数组中字母出现的次数，判断字母出现的次数是否相同。
判断字母是否的方式，两个长度字符串的哈希表使用同一个int[]数组对象进行数据保存，短字符串的字母次数增加，而长字符串的字母数字在哈希表中则减少，如果最终数组元素为0，说明该区域内所有字符出现的次数是相同的。

例子：s1 = "ab" s2 = "dbacd"
刚开始int[]内容 {0,0,0,0,0} - 使用5个长度的数组表示字母个数，真实情况是26
遍历短字符串s1后，计算得到的数组: {1,1,0,0,0}    - 短字符串ab，只在数组的第一个和第二个位置增加
接着遍历s2，使用双指针移动,要减去字母出现的次数：
第一次遍历db子字符串数组后，数组结果为：{1,0,0,-1,0}
第二次遍历ba子字符串，第一个字符d要加回来进行还原，后面的字符a要减少，数组结果为：{0,0,0,0,0}
--》最终得到结果，所有的字母出现的次数都为0

代码实现：

// 判断所有的字母个数是否都是0
bool allZero(std::vector<int> countArr)
{for (int count : countArr){if (count != 0){return false;}}return true;
}bool checkInclusion(string s1, string s2)
{// 长度判断if (s1.length() > s2.length()){return false;}vector<int> countArr(26, 0);for (int i = 0; i < s1.length(); i++){countArr[s1[i] - 'a']++; // 短字符串字母的个数增加countArr[s2[i] - 'a']--; // 长字符串字母的个数减少}// 判断26个字母的所有个数是否都等于0if (allZero(countArr)){return true; // 短字符串s1，和长字符串s2的第一次遍历，就命中了变位词}// 刚开始的几个字符没有命中，继续遍历长字符串后面的字符子数组for (int i = s1.length(); i < s2.length(); i++){countArr[s2[i] - 'a']--;countArr[s2[i - s1.length()] - 'a']++;    // 长字符串，之前减去的字母，进行还原if (allZero(countArr)){return true;}}return false;
}