检查是否可以使用提供的列表中的单词将字符串拆分为句子

Question

我最近偶然发现了编码任务,我一直在努力做到正确.它是这样的:

---

给定非空字符串s和word_list包含非空单词列表的列表,确定是否s可以将其分段为一个或多个字典单词的空格分隔序列.您可以假设word_list它不包含重复项,但每个单词可以多次使用.

例如,给定:

s = 'whataniceday'
word_list = ['a', 'what', 'an', 'nice', 'day']

返回True,因为'whataniceday'可以分段为'what a nice day'.

---

我提出了一个非常幼稚的解决方案,适用于这个特定的例子,但不难让它失败,例如通过向word_list列表中的另一个单词添加一个单词(即['a', 'wha', 'what', 'an', 'nice', 'day']).还有很多其他的东西可能会破坏我的解决方案,但无论如何这里有:

s = "whataniceday"
word_list = ["h", "a", "what", "an", "nice", "day"]

def can_be_segmented(s, word_list):
    tested_str = s
    buildup_str = ''

    for letter in tested_str:        
        buildup_str += letter

        if buildup_str not in word_list:
            continue

        tested_str = tested_str[len(buildup_str):]
        buildup_str = ''

    return bool(tested_str == '' and buildup_str == '')

print(can_be_segmented(s, word_list))

你们知道如何解决这个问题吗？或者也许有更好的方法解决这个问题？

Answer 1

>>> import re
>>> s = 'whataniceday'
>>> word_list = ['a', 'what', 'an', 'nice', 'day']
>>> re.match('^(' + '|'.join(f'({s})' for s in word_list) + ')*$', s)
<_sre.SRE_Match object; span=(0, 12), match='whataniceday'>

作为一个功能:

import re
def can_be_segmented(s, word_list):
    pattern = re.compile('^(' + '|'.join(f'({s})' for s in word_list) + ')*$')
    return pattern.match(s) is not None

这可能是使组非捕获(优化(?:word),而不是(word)使re.match不必保持匹配的单词轨道,但我不打算火候.

如果你的单词不仅仅是字母,你可能想要传递它们re.escape()(f'({re.escape(s)})'而不是f'({s})').

如果你打算使用混合大小写,你希望那些匹配传递re.IGNORECASE或re.I标记(pattern.match(s, re.I)而不是pattern.match(s)).

有关更多信息,请参阅re文档

Answer 2

这是我的解决方案，为了简洁起见，使用生成器表达式和递归

s = "whataniceday"
word_list = ["h", "ani", "a", "what", "an", "nice", "day"]

def can_be_segmented(s, word_list):
    return s == "" or any(
        s.startswith(word) and can_be_segmented(s[len(word):], word_list)
        for word in word_list)

assert can_be_segmented(s, word_list)
assert not can_be_segmented("whataniannicday", word_list)

这段代码表明，如果我们能找到一个单词，使得字符串以该单词开头，并且字符串的其余部分本身可以被分割，那么该字符串就可以被分割。