How can I solve "Existence of a Substring in a String and Its Reverse" efficiently?

You can solve this by reversing the string, storing substrings of length 2 in a hash table, and checking if any of those substrings appear in the reversed string.

What is the time complexity of the solution for "Existence of a Substring in a String and Its Reverse"?

The time complexity is O(n), where n is the length of the string, due to substring generation and comparison using a hash table.

What are some common mistakes when solving "Existence of a Substring in a String and Its Reverse"?

Common mistakes include not reversing the string, incorrectly comparing substrings, and using inefficient data structures for substring lookup.

Can the solution for "Existence of a Substring in a String and Its Reverse" be optimized?

Yes, you can optimize the solution by reducing space complexity in the hash table and ensuring efficient string comparison.

Is there a way to check substrings of a different length in "Existence of a Substring in a String and Its Reverse"?

Yes, you can modify the problem to check for substrings of any length, such as 3 or more, by adjusting the substring generation and comparison logic.

#3083

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

字符串及其反转中是否存在同一子字符串

给你一个字符串 s ，请你判断字符串 s 是否存在一个长度为 2 的子字符串，在 s 反转后的字符串中也出现。如果存在这样的子字符串，返回 true ；如果不存在，返回 false 。示例 1：输入： s = "leetcode" 输出： true 解释：子字符串 "ee" 的长度为 2 ，…

哈希表字符串

题目描述

给你一个字符串 s ，请你判断字符串 s 是否存在一个长度为 2 的子字符串，在 s 反转后的字符串中也出现。

如果存在这样的子字符串，返回 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 仅由小写英文字母组成。

lightbulb

解题思路

方法一：哈希表或数组

我们可以用一个哈希表或者二维数组 $st$ 来存储字符串 $s$ 反转后的所有长度为 $2$ 的子字符串。

然后我们遍历字符串 $s$ ，对于每一个长度为 $2$ 的子字符串，我们判断它是否在 $st$ 中出现过，是则返回 true。否则，遍历结束后返回 false。

时间复杂度 $O(n)$ ，空间复杂度 $O(|\Sigma|^2)$ 。其中 $n$ 为字符串 $s$ 的长度；而 $\Sigma$ 为字符串 $s$ 的字符集，本题中 $\Sigma$ 为小写英文字母，所以 $|\Sigma| = 26$ 。

1

2

3

4

5

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        st = {(a, b) for a, b in pairwise(s[::-1])}
        return any((a, b) in st for a, b in pairwise(s))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently implement a hash table-based solution?
question_mark
Does the candidate show an understanding of string reversal and substring comparison?
question_mark
Is the candidate able to optimize the solution with respect to time and space complexity?

warning

常见陷阱

外企场景

error
Not reversing the string before comparison, which leads to incorrect results.
error
Incorrectly checking substrings, leading to missing valid matches.
error
Using inefficient data structures for substring lookup, causing slower solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider substrings of length 3 instead of 2.
arrow_right_alt
Check if there are any substrings of length 2 that are palindromes.
arrow_right_alt
Optimize the solution by reducing the space complexity of the hash table.

help

常见问题

外企场景

继续练习

#3081 替换字符串中的问号使分数最小 #3085 成为 K 特殊字符串需要删除的最少字符数 #3076 数组中的最短非公共子字符串