2024-09-28:用go语言,给定一个字符串s,要求判断是否存在一个长度为2的子字符串,
在其反转后的字符串中也存在相同的子字符串。
如果存在这样的子字符串,则返回true;
如果不存在,则返回false。
输入:s = "leetcode"。
输出:true。
解释:子字符串 "ee" 的长度为 2,它也出现在 reverse(s) == "edocteel" 中。
答案2024-09-28:
chatgpt
题目来自leetcode3083。
1.我们在主函数main中首先初始化字符串s为"leetcode",然后调用isSubstringPresent来检查是否存在符合条件的子字符串。
2.在isSubstringPresent函数中,我们定义了一个长度为26的数组vis来表示字母的出现情况。我们遍历字符串s,逐个检查相邻的字符对(s[i-1], s[i]), 并将它们转换为对应的数组下标,用位运算来标记存在相同子字符串的情况。如果发现有某个字符已经标记过和当前字符组成的子字符串,那么就返回true。
3.最后,如果遍历完整个字符串后没有发现符合条件的子字符串,那么就返回false。
总的时间复杂度:
总的额外空间复杂度:
通过这种实现,我们可以在线性时间复杂度内解决该问题,并且使用的额外空间非常有限。
package main
import(
"fmt"
)
func isSubstringPresent(s string)bool{
vis :=[26]int{}
for i :=1; i <len(s); i++{
x, y := s[i-1]-'a', s[i]-'a'
vis[x]|=1<< y
if vis[y]>>x&1>0{
returntrue
}
}
returnfalse
}
func main(){
s:="leetcode"
fmt.Println(isSubstringPresent(s))
}
fn is_substring_present(s:&str)->bool{
letmut vis=[0;26];
foriin1..s.len(){
letx= s.as_bytes()[i -1]asusize-'a'asusize;
lety= s.as_bytes()[i]asusize-'a'asusize;
vis[x]|=1<< y;
if vis[y]>> x &1>0{
returntrue;
}
}
false
}
fnmain(){
lets="leetcode";
println!("{}",is_substring_present(s));
}