题目链接
分析
哈希表+位运算优化
可以想到朴素的实现，用两个指针去判断每个长度为 $2$ 的子串反转后是否还存在于原串中
上面的方法中，耗时较长的是遍历字符串去比较是否在原串中存在
我们可以维护一个哈希表，存储每个长度为 $2$ 的子串，这样就仅需 $O(n)$ 的时间判断是否存在于原串中
由于仅包含小写字母，所以我们使用数组 $cnt[26][26]$ 来实现哈希表
进一步的，可以将数组的第二维压缩为一个长度为 $26$ 的二进制数
如果存在字符串 $ab$，则将 $cnt[0]$ 的第二位设置为 $1$
代码实现
class Solution {
public:
bool isSubstringPresent(string s) {
vector<int> cnt(26, 0);
for(int i = 1; i < s.size(); ++i) {
int x = s[i - 1] - 'a', y = s[i] - 'a';
cnt[x] |= 1 << y;
if(cnt[y] >> x & 1)
return true;
}
return false;
}
};
复杂度分析
- 时间复杂度：$O(n + C)$，其中 $n$ 为字符串 $s$ 的长度，$C$ 为字符集大小
- 空间复杂度：$O(C)$
