1

给定一个这样的字符串：

 var str = "thisisinsane";

由字典中的单词列表辅助，例如：

 var dic = [ "insane", "i", "is", "sin", "in", "this", "totally" ];

怎么分str词？

对于此字符串，需要识别 3 个单词。但我们需要避免这些陷阱。大多数时候为了避免它们，我知道我们可以攻击左边的句子，并尝试找到最长的单词。找到后，我们可以攻击字符串的其余部分，等等。

下面：右下角的输入、可能的陷阱和想要的输出。

                      thisisinsane
                          |
                          |
                     (this)isinsane
                     /            \
                    /              \
          (this,i)sinsane         (this,is)insane
              /                     /           \
             /                     /             \
  (this,i,sin)ane          (this,is,in)sane    (this,is,insane)
                                /                   <BEST IS>
                               /                    <THIS ONE>
                       (this,is,in,sane)

最后，我们想要得到：

 var splited = ["this", "is", "insane"];
4

1 回答 1

1

这是一个快速实现，将从左到右进行搜索并首先匹配字典中最长的单词（jsfiddle）。但是，我不太确定自己实现它是否非常聪明，因为这听起来像是一个复杂的领域，即使没有任何关于该主题的知识，我也可以说这个算法一开始就有缺陷。如果有的话，你最好寻找现有的库。

不用说，这只是快速打字。它没有以任何方式针对性能进行优化（它使用递归，这实际上完全没有必要），也没有经过广泛的测试。不过，它适用于您的示例数据，以及我测试的一些变体。我喜欢将一些工作留给 OP，以防我提供完整的代码示例，所以如果你想使用它，请随时改进它。

var splitByDictionary = function (input, dictionary) {
    "use strict";

    // make sure we're going to look for longest-possible matches first
    dictionary.sort( function (a, b) {
        return b.length - a.length;
    } );

    var foundWords = [],
        remaining = input;

    var result = (function match () {
        if( remaining.length === 0 ) {
            return true;
        }

        for( var i = 0; i < dictionary.length; i++ ) {
            if( remaining.substr( 0, dictionary[i].length ) === dictionary[i] ) {
                foundWords.push( dictionary[i] );
                remaining = remaining.substr( dictionary[i].length );

                return match();
            }
        }

        return false;
    })();

    return result ? foundWords : null;
};

var splitted = splitByDictionary( "thisisinsane", ["insane", "i", "is", "sin", "in", "this", "totally"] );
console.log( splitted ); // ["this", "is", "insane"]
于 2013-11-23T00:29:09.517 回答