自学内容网 自学内容网

leetcode 3083. 字符串及其反转中是否存在同一子字符串 简单

给你一个字符串 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)
//著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


原文地址:https://blog.csdn.net/2401_88085478/article/details/144749103

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!