给你一个字符串 s
,请你判断字符串 s
是否存在一个长度为 2
的子字符串,在其反转后的字符串中也出现。
如果存在这样的子字符串,返回 true
;如果不存在,返回 false
。
示例 1:
输入:s = "leetcode"
输出:true
解释:子字符串 "ee"
的长度为 2
,它也出现在 reverse(s) == "edocteel"
中。
示例 2:
输入:s = "abcba"
输出:true
解释:所有长度为 2
的子字符串 "ab"
、"bc"
、"cb"
、"ba"
也都出现在 reverse(s) == "abcba"
中。
示例 3:
输入:s = "abcd"
输出:false
解释:字符串 s
中不存在满足「在其反转后的字符串中也出现」且长度为 2
的子字符串。
提示:
1 <= s.length <= 100
- 字符串
s
仅由小写英文字母组成。
分析:将所有的两位子串视为一个26进制的数,存在哈希表中。之后反向遍历整个字符串,同样将每2位字符转为26进制的数,判断是否在哈希表中出现过即可。
bool isSubstringPresent(char* s) {int l=strlen(s);if(l==1)return false;int temp=(s[0]-'a')*26+s[1]-'a',index=2;int num[10000]={0};num[temp]=1;while(index<l)temp=(temp%26)*26+s[index]-'a',num[temp]=1,index++;int xx=(s[l-1]-'a')*26+s[l-2]-'a';index=l-3;do{if(num[xx]==1)return true;if(index>=0){xx=(xx%26)*26+s[index]-'a',index--;}}while(index>=0);if(num[xx]==1)return true;return false;
}
题解给出的位运算方法。本质上用一个32位整数的位关系来表示相邻字符。由于只关心字符之间的顺序关系,大小只需要26即可。
bool isSubstringPresent(char* s) {int h[26] = {0};int len = strlen(s);for (int i = 0; i + 1 < len; i++) {int x = s[i] - 'a';int y = s[i + 1] - 'a';h[x] |= (1 << y);if ((h[y] >> x) & 1) {return true;}}return false;
}//作者:力扣官方题解
//链接:https://leetcode.cn/problems/existence-of-a-substring-in-a-string-and-its-reverse/solutions/3016932/zi-fu-chuan-ji-qi-fan-zhuan-zhong-shi-fo-ra8p/
//来源:力扣(LeetCode)
//著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。