java - 在字符串集中搜索字符串排列

Question

这个标题有点尴尬；我真的不确定如何总结这一点。我知道我该怎么做，我只是不确定如何有效地做到这一点。这是我的问题:

我有一个字符串作为输入。比方说:

foo bar

我有一组非常大的字符串(数万个)。比方说:

foo, baz, bar, blah, foo bar, foo baz

我需要将输入与集合中的字符串相匹配。在这种情况下，“foo”、“bar”和“foo bar”被视为匹配项。

因此，我需要以某种方式搜索输入的所有排列(它可能超过 2 个单词)，或者以某种方式检测用户是否打算将其(或其中的一部分)放在引号中。或者也许做一些我没有想到的事情。

我可以使用某种数据结构或算法吗？我应该怎么做，或者我不应该处理这个用例？

编辑:上面的错别字扭曲了问题；在上面的示例中，“foo baz”也是一个匹配项。对于那个很抱歉。我基本上想将输入单词的任何排列与字典匹配。因此，输入“abc xyz”会匹配“123 abc”或“abc xyz”或“xyz 123”，但不会匹配“abcxyz”。

Answer 1

我建议使用字典。使用字符串作为键，使用字符串列表作为值。标记将要搜索的字符串，并为每个标记将整个字符串添加到您的字典一次。 (您可以使用 split 方法来标记您的字符串。使用空格作为分隔符。)此后，每当您需要进行查找时，您可以标记搜索字符串并在字典中查找每个标记。

因此，如果您添加了以下字符串:foo、baz、bar、blah、foo bar、foo baz

你的字典有条目:

foo: foo, foo bar, foo baz巴兹:巴兹，富巴兹酒吧:酒吧，酒吧啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦

你是否应该搜索“foo bar”，

您的输出是存储在 foo 和 bar 下的条目的并集，如下所示:"foo bar":= foo, bar

foo: foo, foo bar, foo baz联盟酒吧:酒吧，酒吧

给予:foo, foo bar, foo baz, bar

编辑:我刚刚注意到您只需要完整或部分匹配，即 foo baz 是 Not Acceptable 。简单的解决方案是对结果进行后处理——将搜索字符串和目标字符串中较长的字符串限制为较短字符串的长度，然后将截断的字符串与未修改的字符串进行比较。只接受等价的。

编辑:事实证明 foo baz 确实是一场比赛。忽略上面的段落(第一次编辑)。见(C#)代码如下:

class DictionarySearch
{
    private Dictionary<string, List<string>> dict;

    public DictionarySearch()
    {
        dict = new Dictionary<string, List<string>>();
    }

    /// <summary>
    /// Add a string e.g. foo bar to the dictionary
    /// </summary>
    /// <param name="s">string to be added</param>
    public void addString(string s)
    {
        //tokenize string
        string[] words = s.Split(new char[] { ' ' });

        //add each token to the dictionary as a key with the matching value being s
        foreach (string w in words)
        {
            if (dict.ContainsKey(w))
            {
                dict[w].Add(s);
            }
            else
            {
                dict.Add(w, new List<string>());
                dict[w].Add(s);
            }
        }
    }
    /// <summary>
    /// Find all strings which match at least one token
    /// </summary>
    /// <param name="s">string of tokens (words) to be matched</param>
    /// <returns>List of strings matching at least one word</returns>
    public IList<string> getMatches(string s)
    {
        //split search string into words
        string[] words = s.Split(new char[] { ' ' });
        List<string> output = new List<string>();

        //retrieve from dictionary list of strings matching each word.
        foreach (string w in words)
        {
            if (dict.ContainsKey(w))
            {
                output.AddRange(dict[w]);
            }
            else
            {
                continue;
            }
        }

        return output;
    }
}

给定一个包含 m 个字符串的字典，每个字符串有 q 个单词和 n 个唯一单词，以及一个包含 l 个单词的搜索字符串，时间复杂度如下:

填充数据结构:O(qmT[dictionary-insert])。需要对每个词进行一次插入

查找字符串:O(l*T[dictionary-find])。搜索字符串中每个单词的字典查找。

实际成本取决于您的字典实现。基于哈希表的字典在插入和查找时都会产生 O(1) 的成本。基于二叉树的字典的插入和查找成本均为 O(lg n)。