3083. Existence of a Substring in a String and Its Reverse
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 inreverse(s) == "edocteel".
Example 2:
Input:
s = "abcba"
Output:true
Explanation: All of the substrings of length 2"ab","bc","cb","ba"are also present inreverse(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 <= 100sconsists only of lowercase English letters.
Test Cases
class Solution:
def isSubstringPresent(self, s: str) -> bool: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
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
评论需要 JavaScript。