Easy

题目描述

给定一个字符串 s，找到任何一个长度为 2 的子字符串，该子字符串在 s 的反转中也存在。

如果存在这样的子字符串，返回 true，否则返回 false。

示例 1：

输入：s = "leetcode"
输出：true
解释：长度为 2 的子字符串 "ee" 在 reverse(s) == "edocteel" 中也存在。

示例 2：

输入：s = "abcba"
输出：true
解释：所有长度为 2 的子字符串 "ab", "bc", "cb", "ba" 在 reverse(s) == "abcba" 中也都存在。

示例 3：

输入：s = "abcd"
输出：false
解释：s 中没有长度为 2 的子字符串在 s 的反转中也存在。

约束条件：

  • 1 <= s.length <= 100
  • s 只包含小写英文字母

提示：

  • 通过反转字符串 s 创建一个新字符串
  • 对于 s 中每个长度为 2 的子字符串，检查在 s 的反转中是否有对应的子字符串

解题思路

解题思路

这道题要求找到一个长度为 2 的子字符串，既存在于原字符串中，也存在于反转字符串中。

方法一：哈希表存储

  1. 遍历原字符串，将所有长度为 2 的子字符串存储到哈希集合中
  2. 遍历反转字符串，检查每个长度为 2 的子字符串是否在哈希集合中
  3. 如果找到匹配的子字符串，返回 true

方法二：直接构造反转字符串（推荐）

  1. 构造原字符串的反转字符串
  2. 遍历原字符串的所有长度为 2 的子字符串
  3. 检查每个子字符串是否在反转字符串中出现
  4. 使用字符串的 find 方法或手动遍历来检查

方法三：优化的双指针 考虑到长度为 2 的子字符串 s[i:i+2] 在反转字符串中存在，意味着反转字符串中某个位置有相同的两个连续字符。我们可以直接在原字符串中寻找这样的模式。

由于字符串长度不超过 100，时间复杂度不是关键因素，方法二最直观易懂，是推荐解法。

代码实现

class Solution {
public:
    bool isSubstringPresent(string s) {
        if (s.length() < 2) return false;
        
        string reversed = s;
        reverse(reversed.begin(), reversed.end());
        
        for (int i = 0; i < s.length() - 1; i++) {
            string substr = s.substr(i, 2);
            if (reversed.find(substr) != string::npos) {
                return true;
            }
        }
        
        return false;
    }
};

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        if len(s) < 2:
            return False
        
        reversed_s = s[::-1]
        
        for i in range(len(s) - 1):
            substr = s[i:i+2]
            if substr in reversed_s:
                return True
        
        return False

public class Solution {
    public bool IsSubstringPresent(string s) {
        if (s.Length < 2) return false;
        
        string reversed = new string(s.Reverse().ToArray());
        
        for (int i = 0; i < s.Length - 1; i++) {
            string substr = s.Substring(i, 2);
            if (reversed.Contains(substr)) {
                return true;
            }
        }
        
        return false;
    }
}

var isSubstringPresent = function(s) {
    if (s.length < 2) return false;
    
    const reversed = s.split('').reverse().join('');
    
    for (let i = 0; i < s.length - 1; i++) {
        const substr = s.substring(i, i + 2);
        if (reversed.includes(substr)) {
            return true;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²)
空间复杂度O(n)

说明：

  • 时间复杂度：O(n²)，其中 n 是字符串长度。需要遍历 n-1 个长度为 2 的子字符串，每次在反转字符串中查找的时间复杂度为 O(n)
  • 空间复杂度：O(n)，存储反转字符串需要 O(n) 的额外空间