LeetCode 字符串高频题解：差异检测、子串匹配与异位词判定
本篇整理四道经典字符串算法题的高效解法，涵盖字符频次统计、暴力匹配优化、排序对比及周期性子串验证等核心思路。
389. 找不同 —— 频次差值定位法
给定两个仅含小写字母的字符串 s 和 t，其中 t 是 s 添加一个字符后打乱顺序所得。需找出被添加的字符。
解法利用字符频次差：先统计 s 中各字母出现次数；再遍历 t，对每个字符递减计数；首次出现负值即为答案。
class StringDiffSolver {
public:
char locateAddedChar(const std::string& base, const std::string& extended) {
std::vector<int> freq(26, 0);
for (char c : base) freq[c - 'a']++;
for (char c : extended) {
if (--freq[c - 'a'] < 0) return c;
}
return '\0';
}
};28. 找出字符串中第一个匹配项的下标 —— 滑动窗口暴力匹配
在主串 haystack 中查找子串 needle 的首次出现位置，未找到返回 -1。
采用朴素匹配策略：枚举所有可能起始位置 i（范围 [0, m-n]），逐字符比对长度为 n 的窗口内容。
class SubstringMatcher {
public:
int findFirstOccurrence(const std::string& text, const std::string& pattern) {
int lenText = text.length(), lenPat = pattern.length();
if (lenPat == 0) return 0;
for (int start = 0; start <= lenText - lenPat; ++start) {
bool matched = true;
for (int offset = 0; offset < lenPat; ++offset) {
if (text[start + offset] != pattern[offset]) {
matched = false;
break;
}
}
if (matched) return start;
}
return -1;
}
};242. 有效的字母异位词 —— 双频次校验或排序判等
判断两字符串是否互为字母异位词（字符种类与数量完全相同，顺序可不同）。
方法一：哈希计数
初始化 26 维整型数组记录 a-z 出现频次。先累加 s，再递减 t；若任一位置变为负数则非法；最终全零即合法。
class AnagramChecker {
public:
bool isValidAnagram(const std::string& a, const std::string& b) {
if (a.length() != b.length()) return false;
std::vector<int> count(26, 0);
for (char c : a) count[c - 'a']++;
for (char c : b) {
if (--count[c - 'a'] < 0) return false;
}
return true;
}
};方法二：排序后比较
时间复杂度略高但代码极简：分别排序两字符串并直接比较是否相等。
bool checkBySorting(const std::string& x, const std::string& y) {
if (x.length() != y.length()) return false;
std::string sortedX = x, sortedY = y;
std::sort(sortedX.begin(), sortedX.end());
std::sort(sortedY.begin(), sortedY.end());
return sortedX == sortedY;
}459. 重复的子字符串 —— 枚举因子长度验证周期性
判断字符串能否由其某个非空真子串重复多次构成。
枚举所有可能的子串长度 len（从 1 到 n/2），仅当 n % len == 0 时才验证：检查字符串是否满足 s[i] == s[i % len] 对所有 i 成立。
class RepeatedPatternDetector {
public:
bool hasRepeatedPattern(const std::string& str) {
int n = str.length();
for (int segLen = 1; segLen <= n / 2; ++segLen) {
if (n % segLen != 0) continue;
bool valid = true;
for (int i = 0; i < n; ++i) {
if (str[i] != str[i % segLen]) {
valid = false;
break;
}
}
if (valid) return true;
}
return false;
}
};