Hard

题目描述

给你两个字符串数组 wordsContainer 和 wordsQuery。

对于每个 wordsQuery[i]，你需要从 wordsContainer 中找到一个与 wordsQuery[i] 有最长公共后缀的字符串。如果 wordsContainer 中有两个或更多字符串共享最长的公共后缀，则找到长度最小的字符串。如果有两个或更多这样长度相同的最小字符串，则找到在 wordsContainer 中出现较早的那个。

返回一个整数数组 ans，其中 ans[i] 是 wordsContainer 中与 wordsQuery[i] 有最长公共后缀的字符串的索引。

示例 1：

输入：wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]
输出：[1,1,1]
解释：
- 对于 wordsQuery[0] = "cd"，共享最长公共后缀 "cd" 的字符串在索引 0、1 和 2。其中索引 1 的字符串长度最短为 3。
- 对于 wordsQuery[1] = "bcd"，共享最长公共后缀 "bcd" 的字符串在索引 0、1 和 2。其中索引 1 的字符串长度最短为 3。
- 对于 wordsQuery[2] = "xyz"，没有字符串共享公共后缀。因此最长公共后缀是 ""，索引 0、1 和 2 都共享。其中索引 1 的字符串长度最短为 3。

示例 2：

输入：wordsContainer = ["abcdefgh","poiuygh","ghghgh"], wordsQuery = ["gh","acbfgh","acbfegh"]
输出：[2,0,2]

约束条件：

  • 1 <= wordsContainer.length, wordsQuery.length <= 10^4
  • 1 <= wordsContainer[i].length <= 5 * 10^3
  • 1 <= wordsQuery[i].length <= 5 * 10^3
  • wordsContainer[i] 仅包含小写英文字母
  • wordsQuery[i] 仅包含小写英文字母
  • wordsContainer[i] 长度总和最多为 5 * 10^5
  • wordsQuery[i] 长度总和最多为 5 * 10^5

解题思路

解题思路

这道题要求找到最长公共后缀，可以通过以下几种方法解决：

方法1：字典树（推荐）

根据题目提示，如果我们将字符串反转，问题就转化为寻找最长公共前缀。我们可以构建一个字典树（Trie）：

  1. 构建反向字典树：将所有 wordsContainer 中的字符串反转后插入字典树
  2. 记录最优索引：在字典树的每个节点上，记录经过该节点的所有字符串中最优的索引（按照题目要求的优先级：最短长度 → 最早出现）
  3. 查询过程：对于每个查询字符串，反转后在字典树中尽可能深地匹配，返回匹配到的最深节点的最优索引

方法2：暴力匹配

对于每个查询字符串，遍历所有容器字符串，计算公共后缀长度，选择最优的索引。时间复杂度较高但实现简单。

字典树方法的优势在于：

  • 时间复杂度更优：O(总字符串长度)
  • 空间复杂度合理：O(总字符串长度)
  • 能够高效处理大量查询

关键点是在字典树节点中维护最优索引的更新逻辑：优先选择长度最短的字符串，长度相同时选择索引最小的。

代码实现

class Solution {
public:
    struct TrieNode {
        TrieNode* children[26];
        int bestIndex;
        
        TrieNode() {
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
            bestIndex = -1;
        }
    };
    
    vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
        TrieNode* root = new TrieNode();
        
        // Build trie with reversed strings
        for (int i = 0; i < wordsContainer.size(); i++) {
            string& word = wordsContainer[i];
            TrieNode* node = root;
            
            // Update root with best index
            if (root->bestIndex == -1 || word.length() < wordsContainer[root->bestIndex].length() ||
                (word.length() == wordsContainer[root->bestIndex].length() && i < root->bestIndex)) {
                root->bestIndex = i;
            }
            
            // Insert reversed string
            for (int j = word.length() - 1; j >= 0; j--) {
                int ch = word[j] - 'a';
                if (node->children[ch] == nullptr) {
                    node->children[ch] = new TrieNode();
                }
                node = node->children[ch];
                
                // Update best index at current node
                if (node->bestIndex == -1 || word.length() < wordsContainer[node->bestIndex].length() ||
                    (word.length() == wordsContainer[node->bestIndex].length() && i < node->bestIndex)) {
                    node->bestIndex = i;
                }
            }
        }
        
        vector<int> result;
        // Process queries
        for (string& query : wordsQuery) {
            TrieNode* node = root;
            int bestIndex = root->bestIndex;
            
            // Traverse as far as possible
            for (int j = query.length() - 1; j >= 0; j--) {
                int ch = query[j] - 'a';
                if (node->children[ch] == nullptr) {
                    break;
                }
                node = node->children[ch];
                bestIndex = node->bestIndex;
            }
            
            result.push_back(bestIndex);
        }
        
        return result;
    }
};

class Solution:
    def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:
        class TrieNode:
            def __init__(self):
                self.children = {}
                self.best_index = -1
        
        root = TrieNode()
        
        # Build trie with reversed strings
        for i, word in enumerate(wordsContainer):
            node = root
            
            # Update root with best index
            if (root.best_index == -1 or 
                len(word) < len(wordsContainer[root.best_index]) or
                (len(word) == len(wordsContainer[root.best_index]) and i < root.best_index)):
                root.best_index = i
            
            # Insert reversed string
            for j in range(len(word) - 1, -1, -1):
                ch = word[j]
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
                
                # Update best index at current node
                if (node.best_index == -1 or 
                    len(word) < len(wordsContainer[node.best_index]) or
                    (len(word) == len(wordsContainer[node.best_index]) and i < node.best_index)):
                    node.best_index = i
        
        result = []
        # Process queries
        for query in wordsQuery:
            node = root
            best_index = root.best_index
            
            # Traverse as far as possible
            for j in range(len(query) - 1, -1, -1):
                ch = query[j]
                if ch not in node.children:
                    break
                node = node.children[ch]
                best_index = node.best_index
            
            result.append(best_index)
        
        return result

public class Solution {
    public class TrieNode {
        public TrieNode[] children;
        public int bestIndex;
        
        public TrieNode() {
            children = new TrieNode[26];
            bestIndex = -1;
        }
    }
    
    public int[] StringIndices(string[] wordsContainer, string[] wordsQuery) {
        TrieNode root = new TrieNode();
        
        // Build trie with reversed strings
        for (int i = 0; i < wordsContainer.Length; i++) {
            string word = wordsContainer[i];
            TrieNode node = root;
            
            // Update root with best index
            if (root.bestIndex == -1 || word.Length < wordsContainer[root.bestIndex].Length ||
                (word.Length == wordsContainer[root.bestIndex].Length && i < root.bestIndex)) {
                root.bestIndex = i;
            }
            
            // Insert reversed string
            for (int j = word.Length - 1; j >= 0; j--) {
                int ch = word[j] - 'a';
                if (node.children[ch] == null) {
                    node.children[ch] = new TrieNode();
                }
                node = node.children[ch];
                
                // Update best index at current node
                if (node.bestIndex == -1 || word.Length < wordsContainer[node.bestIndex].Length ||
                    (word.Length == wordsContainer[node.bestIndex].Length && i < node.bestIndex)) {
                    node.bestIndex = i;
                }
            }
        }
        
        int[] result = new int[wordsQuery.Length];
        // Process queries
        for (int i = 0; i < wordsQuery.Length; i++) {
            string query = wordsQuery[i];
            TrieNode node = root;
            int bestIndex = root.bestIndex;
            
            // Traverse as far as possible
            for (int j = query.Length - 1; j >= 0; j--) {
                int ch = query[j] - 'a';
                if (node.children[ch] == null) {
                    break;
                }
                node = node.children[ch];
                bestIndex = node.bestIndex;
            }
            
            result[i] = bestIndex;
        }
        
        return result;
    }
}

var stringIndices = function(wordsContainer, wordsQuery) {
    class TrieNode {
        constructor() {
            this.children = {};
            this.bestIndex = -1;
            this.bestLength = Infinity;
        }
    }
    
    const root = new TrieNode();
    
    // Build suffix trie
    for (let i = 0; i < wordsContainer.length; i++) {
        const word = wordsContainer[i];
        for (let j = word.length - 1; j >= 0; j--) {
            let node = root;
            for (let k = j; k < word.length; k++) {
                const char = word[k];
                if (!node.children[char]) {
                    node.children[char] = new TrieNode();
                }
                node = node.children[char];
                
                // Update best candidate for this suffix
                if (word.length < node.bestLength || 
                    (word.length === node.bestLength && i < node.bestIndex) ||
                    node.bestIndex === -1) {
                    node.bestIndex = i;
                    node.bestLength = word.length;
                }
            }
        }
    }
    
    // Update root with best overall candidate
    for (let i = 0; i < wordsContainer.length; i++) {
        const word = wordsContainer[i];
        if (word.length < root.bestLength || 
            (word.length === root.bestLength && i < root.bestIndex) ||
            root.bestIndex === -1) {
            root.bestIndex = i;
            root.bestLength = word.length;
        }
    }
    
    const result = [];
    
    for (const query of wordsQuery) {
        let node = root;
        let lastValidIndex = root.bestIndex;
        
        // Try to match suffix of query
        for (let i = query.length - 1; i >= 0; i--) {
            const char = query[i];
            if (node.children[char]) {
                node = node.children[char];
                lastValidIndex = node.bestIndex;
            } else {
                break;
            }
        }
        
        result.push(lastValidIndex);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型字典树解法
时间复杂度O(S + Q)，其中 S 是所有容器字符串的总长度，Q 是所有查询字符串的总长度
空间复杂度O(S)，用于存储字典树结构

相关题目