prefix - 确定一个字符串是否是另一个字符串的前缀

Question

我已经写下了一个简单的函数来确定 str1 是否是 str2 的前缀。这是一个非常简单的函数，看起来像这样(在 JS 中):

function isPrefix(str1, str2) // determine if str1 is a prefix of a candidate string
{
    if(str2.length < str1.length) // candidate string can't be smaller than prefix string 
        return false;

    var i = 0;
    while(str1.charAt(i) == str2.charAt(i) && i <= str1.length)
        i++;
   if(i < str1.length) // i terminated => str 1 is smaller than str 2
        return false;
    return true;
}

如您所见，它遍历前缀字符串的整个长度以判断它是否是候选字符串的前缀。这意味着它的复杂性是 O(N)，这还不错，但是当我有一个庞大的数据集要考虑循环以确定哪些字符串具有前缀字符串作为前缀的一部分时，这会成为一个问题。这使得复杂性倍增，如 O(M*N)，其中 M 是给定数据集中的字符串总数。不好。

我在 Internet 上进行了一些探索，以确定最佳答案是 Patricia/​​Radix 树。字符串存储为前缀的地方。即便如此，当我尝试插入/查找字符串时，如果我使用前面提到的前缀测量功能，字符串匹配也会有相当大的开销。

假设我有一个前缀字符串 'rom' 和一组候选词

var dataset =["random","rapid","romance","romania","rome","rose"];

在基数树中会这样:

         r
       /    \
     a       o
    / \     / \
ndom pid  se  m
             / \
           an   e
          /  \
        ia   ce

这意味着，对于每个节点，我将使用前缀匹配函数来确定哪个节点的值与索引处的前缀字符串匹配。不知何故，这个解决方案似乎仍然很困难，对我来说不太合适。有什么更好的或者无论如何我可以改进核心前缀匹配功能吗？

Answer 1

看起来你有两个不同的问题。

一种是确定一个字符串是否作为前缀包含在另一个字符串中。为此，我建议使用已经在该语言的字符串库中实现的函数。在 JavaScript 中你可以这样做

if (str2.indexOf(str1) === 0) {
    // string str1 is a prefix of str2
}

在此处查看 String.indexOf 的文档: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/indexOf

对于另一个问题，在一堆字符串中，找出哪些字符串以给定的字符串作为前缀，如果您想要快速查找，构建像 Trie 或您提到的数据结构似乎是要走的路。