Problem

Given a string s, find any substring of length 2 which is also present in the reverse of s.

A substring is a contiguous sequence of characters within a string.

Return true if such a substring exists, and false otherwise.

https://leetcode.cn/problems/existence-of-a-substring-in-a-string-and-its-reverse/

Example 1:

Input: s = "leetcode"
Output: true
Explanation: Substring "ee" is of length 2 which is also present in reverse(s) == "edocteel".

Example 2:

Input: s = "abcba"
Output: true
Explanation: All of the substrings of length 2 "ab", "bc", "cb", "ba" are also present in reverse(s) == "abcba".

Example 3:

Input: s = "abcd"
Output: false
Explanation: There is no substring of length 2 in s, which is also present in the reverse of s.

Constraints:

  • 1 <= s.length <= 100
  • s consists only of lowercase English letters.

Test Cases

1
2
class Solution:
def isSubstringPresent(self, s: str) -> bool:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
import pytest

from solution import Solution


@pytest.mark.parametrize('s, expected', [
("leetcode", True),
("abcba", True),
("abcd", False),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, s, expected):
assert sol.isSubstringPresent(s) == expected

Thoughts

扫描 s 中所有长度为 2 的子字符串,加入哈希集合。同时检查这个子字符串翻转之后是否也在集合中,在就返回 true。

显然并不用先把所有长度为 2 的子字符串都添加完再做判定,可以一边加一边比较。

Code

solution.py
1
2
3
4
5
6
7
8
9
10
class Solution:
def isSubstringPresent(self, s: str) -> bool:
pairs: set[str] = set()
for i in range(len(s) - 1):
t = s[i:i+2]
pairs.add(t)
if t[::-1] in pairs:
return True

return False