字符串及其反转中是否存在同一子字符串
难度:
标签:
题目描述
Given a string s, find any substring of length 2 which is also present in the reverse of s.
Return true if such a substring exists, and false otherwise.
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 <= 100sconsists only of lowercase English letters.
代码结果
运行时间: 16 ms, 内存: 16.0 MB
/*
* 思路：
* 1. 反转字符串s得到reverseS。
* 2. 使用Java Stream API遍历所有长度为2的子字符串，并检查这些子字符串是否存在于reverseS中。
* 3. 如果存在这样的子字符串，返回true；否则，返回false。
*/
import java.util.stream.IntStream;
public class Solution {
public boolean hasReverseSubstring(String s) {
// 获取反转后的字符串
String reverseS = new StringBuilder(s).reverse().toString();
// 使用流API检查是否存在符合条件的子字符串
return IntStream.range(0, s.length() - 1)
.mapToObj(i -> s.substring(i, i + 2))
.anyMatch(reverseS::contains);
}
}
解释
方法:
该题解采用了一个简单的遍历和查找的方法。首先，对字符串s进行从头至尾的遍历，每次取出一个长度为2的子字符串，并检查这个子字符串是否存在于字符串s的反转字符串中。如果找到至少一个这样的子字符串，则立即返回true；如果遍历完成后没有找到任何匹配的子字符串，则返回false。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么选择长度为2的子字符串进行检查，而不是其他长度？
▷🦆
反转字符串后，子字符串在原字符串和反转字符串中的相对位置是否影响结果的判断？
▷🦆
该算法是否考虑了所有可能的边界情况，例如字符串长度为1或包含重复字符的情况？
▷