2024-09-07:用go语言,给定一个包含 n 个非空字符串的数组 arr,你的任务是找出一个长度为 n 的字符串数组 answer。
对于每个索引 i,answer[i] 是 arr[i] 的最短子字符串,并且这个子字符串不是 arr 中其他字符串的子字符串。
如果有多个这样的子字符串,则选择字典序最小的一个。
如果不存在这样的子字符串,则对应位置的 answer[i] 应为一个空字符串。
你需要编写一个算法来实现以上要求,并返回生成的字符串数组 answer。
输入:arr = ["cab","ad","bad","c"]。
输出:["ab","","ba",""]。
解释:求解过程如下:
对于字符串 "cab" ,最短没有在其他字符串中出现过的子字符串是 "ca" 或者 "ab" ,我们选择字典序更小的子字符串,也就是 "ab" 。
对于字符串 "ad" ,不存在没有在其他字符串中出现过的子字符串。
对于字符串 "bad" ,最短没有在其他字符串中出现过的子字符串是 "ba" 。
对于字符串 "c" ,不存在没有在其他字符串中出现过的子字符串。
chatgpt
题目来自leetcode3076。
大体步骤如下:
Go完整代码如下:
package main
import(
"fmt"
"strings"
)
func shortestSubstrings(arr []string)[]string{
ans :=make([]string,len(arr))
for i, s :=range arr {
m :=len(s)
res :=""
for size :=1; size <= m && res ==""; size++{
next:
for k := size; k <= m; k++{
sub:= s[k-size : k]
if res !=""&&sub>= res {
continue
}
for j, t :=range arr {
if j != i && strings.Contains(t,sub){
continuenext
}
}
res =sub
}
}
ans[i]= res
}
return ans
}
func main(){
arr :=[]string{"cab","ad","bad","c"}
fmt.Println(shortestSubstrings(arr))
}
在这里插入图片描述Rust完整代码如下:
use std::collections::HashSet;
fnshortest_substrings(arr:Vec<&str>)->Vec<String>{
letmut ans=vec![String::new(); arr.len()];
for(i, s)in arr.iter().enumerate(){
letm= s.len();
letmut res=String::new();
forsizein1..=m {
if!res.is_empty(){
break;
}
forkin size..=m {
letsub=&s[k - size..k];
if!res.is_empty()&& sub >= res.as_str(){
continue;
}
letmut found=false;
for(j, t)in arr.iter().enumerate(){
if j != i && t.contains(sub){
found =true;
break;
}
}
if!found {
res = sub.to_string();
}
}
}
ans[i]= res;
}
ans
}
fnmain(){
letarr=vec!["cab","ad","bad","c"];
println!("{:?}",shortest_substrings(arr));
}
在这里插入图片描述
领取专属 10元无门槛券
私享最新 技术干货