2024-10-26：最长公共后缀查询。用go语言，给定两个字符串数组 wordsContainer 和 wordsQuery，

2024-10-26：最长公共后缀查询。用go语言，给定两个字符串数组 wordsContainer 和 wordsQuery，要对每个 wordsQuery[i] 找到一个与其有最长公共后缀的字符串。如果有多个字符串与 wordsQuery[i] 有相同的最长公共后缀，则返回在 wordsContainer 中最早出现的那个。最后，返回一个整数数组 ans，其中 ans[i] 表示与 wordsQuery[i] 有最长公共后缀的字符串在 wordsContainer 中的下标。

输入：wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]。

输出：[1,1,1]。

解释：

我们分别来看每一个 wordsQuery[i] ：

对于 wordsQuery[0] = "cd" ，wordsContainer 中有最长公共后缀 "cd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。

对于 wordsQuery[1] = "bcd" ，wordsContainer 中有最长公共后缀 "bcd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。

对于 wordsQuery[2] = "xyz" ，wordsContainer 中没有字符串跟它有公共后缀，所以最长公共后缀为 "" ，下标为 0 ，1 和 2 的字符串都得到这一公共后缀。这些字符串中， 答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。

答案2024-10-26：

chatgpt

题目来自leetcode3093。

大体步骤如下：

1.初始化数据结构：

• 创建一个结果数组ans，其长度与wordsQuery相同，用于存放每个查询的结果索引。

• 在遍历wordsContainer时记录每个字符串的索引和长度，便于后续比较。

2.处理每一个查询字符串：

• 遍历wordsQuery中的每个字符串，比如wordsQuery[i]。

• 对于每个查询字符串，初始化当前最长公共后缀的长度 (maxLen) 为0，和对应的字符串索引 (bestIndex)。

3.与每一个容器字符串比较：

• 对于每个查询字符串，遍历wordsContainer中的所有字符串。

• 从当前查询字符串的尾部开始向前检查与当前wordsContainer[j]的后缀匹配。

• 计算两个字符串，从尾部开始的最大匹配长度。

• 若发现新的公共后缀长度大于maxLen，则更新maxLen和bestIndex为当前字符串的索引。

• 如果发现公共后缀长度等于当前的maxLen，则比较wordsContainer[j]和wordsContainer[bestIndex]的长度：

• 如果wordsContainer[j]更短，则更新bestIndex。

4.处理没有匹配的情况：

• 如果没有匹配，则maxLen将保持为0，bestIndex将在初始状态。

• 根据预定规则，将bestIndex更新为1，表示第一个有效字符串的索引。

5.填充结果数组：

• 将确定的bestIndex存入结果数组ans[i]。

6.完成遍历：

• 重复步骤2到步骤5，直到遍历完所有的wordsQuery。

7.返回结果：

• 返回填充完整的结果数组ans。

复杂度分析

1.时间复杂度：

• 对于每个查询字符串（假设有m个查询），我们需要遍历每个容器字符串（假设有n个字符串）。

• 每次比较可能最多需要遍历两个字符串的长度（设最坏情况，两个字符串长度均近似于L），因此时间复杂度为：O(mnL)

• 这里的O(n \times L)是对每个查询遍历所有容器字符串的时间。

2.空间复杂度：

• 由于只使用了一个结果数组ans，其大小为m，额外的不常数空间基本上是常量级别。

• 因此，总的额外空间复杂度为：(O(m))

• 不考虑输入数组本身占用的空间。

总结

•时间复杂度： O(mnL)

•空间复杂度： (O(m))

这个分析为你构建解决方案提供了清晰的逻辑框架，并明确了复杂度考量。

Go完整代码如下：

package main

import(

"fmt"

"math"

)

func stringIndices(wordsContainer, wordsQuery []string)[]int{

type node struct{

son     [26]*node

minL, i int

}

root :=&node{minL: math.MaxInt}

for idx, s :=range wordsContainer {

l :=len(s)

cur := root

if l < cur.minL {

cur.minL, cur.i = l, idx

}

for i :=len(s)-1; i >=0; i--{

b := s[i]-'a'

if cur.son[b]==nil{

cur.son[b]=&node{minL: math.MaxInt}

}

cur = cur.son[b]

if l < cur.minL {

cur.minL, cur.i = l, idx

}

}

}

ans :=make([]int,len(wordsQuery))

for idx, s :=range wordsQuery {

cur := root

for i :=len(s)-1; i >=0&& cur.son[s[i]-'a']!=nil; i--{

cur = cur.son[s[i]-'a']

}

ans[idx]= cur.i

}

return ans

}

func main(){

wordsContainer :=[]string{"abcd","bcd","xbcd"}

wordsQuery :=[]string{"cd","bcd","xyz"}

fmt.Println(stringIndices(wordsContainer, wordsQuery))

}

在这里插入图片描述Rust完整代码如下：

use std::cmp::Ordering;

structNode{

son:[Option<Box<Node>>;26],

min_l:usize,

index:usize,

}

implNode{

fnnew()->Self{

Node{

son:Default::default(),

min_l: usize::MAX,

index: usize::MAX,

}

}

}

fnstring_indices(words_container:Vec<&str>, words_query:Vec<&str>)->Vec<usize>{

letmut root=Node::new();

for(idx, s)in words_container.iter().enumerate(){

letl= s.len();

letmut cur=&mut root;

if l < cur.min_l {

cur.min_l = l;

cur.index = idx;

}

forchin s.chars().rev(){

letb=(ch asusize)-('a'asusize);

if cur.son[b].is_none(){

cur.son[b]=Some(Box::new(Node::new()));

}

cur = cur.son[b].as_mut().unwrap();

if l < cur.min_l {

cur.min_l = l;

cur.index = idx;

}

}

}

letmut ans=vec![0; words_query.len()];

for(idx, s)in words_query.iter().enumerate(){

letmut cur=&mut root;

forchin s.chars().rev(){

letb=(ch asusize)-('a'asusize);

if cur.son[b].is_none(){

break;

}

cur = cur.son[b].as_mut().unwrap();

}

ans[idx]= cur.index;

}

ans

}

fnmain(){

letwords_container=vec!["abcd","bcd","xbcd"];

letwords_query=vec!["cd","bcd","xyz"];

letresult=string_indices(words_container, words_query);

println!("{:?}", result);

}

在这里插入图片描述