2024-10-26：最长公共后缀查询。用 go 语言，给定两个字符串数组 wordsContainer 和 wordsQuery，要对每个 wordsQuery[i] 找到一个与其有最长公共后缀的字符串

2024-10-26
北京
本文字数：2660 字
阅读完需：约 9 分钟

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;
struct Node {    son: [Option<Box<Node>>; 26],    min_l: usize,    index: usize,}
impl Node {    fn new() -> Self {        Node {            son: Default::default(),            min_l: usize::MAX,            index: usize::MAX,        }    }}
fn string_indices(words_container: Vec<&str>, words_query: Vec<&str>) -> Vec<usize> {    let mut root = Node::new();
    for (idx, s) in words_container.iter().enumerate() {        let l = s.len();        let mut cur = &mut root;
        if l < cur.min_l {            cur.min_l = l;            cur.index = idx;        }
        for ch in s.chars().rev() {            let b = (ch as usize) - ('a' as usize);            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;            }        }    }
    let mut ans = vec![0; words_query.len()];
    for (idx, s) in words_query.iter().enumerate() {        let mut cur = &mut root;
        for ch in s.chars().rev() {            let b = (ch as usize) - ('a' as usize);            if cur.son[b].is_none() {                break;            }            cur = cur.son[b].as_mut().unwrap();        }        ans[idx] = cur.index;    }
    ans}
fn main() {    let words_container = vec!["abcd", "bcd", "xbcd"];    let words_query = vec!["cd", "bcd", "xyz"];    let result = string_indices(words_container, words_query);
    println!("{:?}", result);}