题目描述
给你一个字符串 s
,请你判断字符串 s
是否存在一个长度为 2
的子字符串,在其反转后的字符串中也出现。
如果存在这样的子字符串,返回 true
;如果不存在,返回 false
。
样例
输入:s = "leetcode"
输出:true
解释:子字符串 "ee" 的长度为 2,它也出现在 reverse(s) == "edocteel" 中。
输入:s = "abcba"
输出:true
解释:所有长度为 2 的子字符串 "ab"、"bc"、"cb"、"ba" 也都出现在 reverse(s) == "abcba" 中。
输入:s = "abcd"
输出:false
解释:字符串 s 中不存在满足「在其反转后的字符串中也出现」且长度为 2 的子字符串。
限制
1 <= s.length <= 100
- 字符串
s
仅由小写英文字母组成。
算法
(哈希表) $O(n)$
- 定义哈希表,将长度为 2 的字符串映射到 $0$ 到 $26^2-1$ 的位置中。
- 遍历字符串,将长度为 2 的子串插入到哈希表中。
- 遍历字符串,在哈希表中查找是否存在长度为 2 逆序子串。
时间复杂度
- 预处理哈希表的时间复杂度为 $O(n)$,查询的总时间复杂度为 $O(n)$。
- 故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表。
C++ 代码
class Solution {
public:
bool isSubstringPresent(string s) {
const int n = s.size();
unordered_set<int> seen;
for (int i = 0; i < n - 1; i++) {
int h = (s[i] - 'a') * 26 + s[i + 1] - 'a';
seen.insert(h);
}
for (int i = n - 1; i >= 1; i--) {
int h = (s[i] - 'a') * 26 + s[i - 1] - 'a';
if (seen.find(h) != seen.end())
return true;
}
return false;
}
};