我已经用以下代码解决了Word Break问题:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False] * n
for i in range(n):
for j in range(i + 1, n + 1):
if (s[i : j] in wordDict) and (i == 0 or dp[i - 1]):
dp[j - 1] = True
return dp[n - 1]
我正在尝试将其编写为列表理解,以使其“或多或少是一行代码”。
我一直试图将
dp
表达如下:
dp = [True if (s[i:j] in wordDict) and (i==0 or dp[i-1]) for j in range(i+1, n+1) for i in range(n) else False]
但是,我有点陷入困境,因为在原始代码中它被设置为
dp[j - 1] = True
,而我无法通过列表理解来完成它。
我知道编写一大段代码作为列表理解并不是一个好主意(我也很困惑),但这只是为了教育目的。
事实上,随着
dp
被写入,不仅如此,那些新写入的值在下一次迭代中再次被 read ,这不会是列表理解的候选者。
然而,如果您愿意牺牲一些 Python 最佳实践,您就可以接近。
首先,您可以将内部循环转换为列表理解:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False] * n
for i in range(n):
dp[i:] = [dp[j] or
(s[i:j+1] in wordDict) and (i == 0 or dp[i-1])
for j in range(i, n)]
return dp[-1]
让我们稍微改变一下算法,这样列表覆盖就从索引 0 开始,而不是从索引 i 开始。相反,我们逐渐缩短列表。同时,我们将
dp[0]
指定为从上一次迭代中读取的值,因此我们还将其作为初始列表的前缀:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [True] + [False] * n
for i in range(n):
dp = [dp[j-i+1] or s[i:j+1] in wordDict and dp[0]
for j in range(i, n)]
return dp[0]
但是
dp =
原则上会阻碍列表理解的更广泛使用。
你可以使用 a-Pythonic 函数来解决这个问题,它会改变并返回一些东西:
def assign(self, target, source):
target[:] = source # mutate the target
return target[-1] # for our purposes we only need it to return the last value
现在我们可以将其包含在更大的列表理解表达式中:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [True] + [False] * n
return [
self.assign(dp, [dp[j-i+1] or s[i:j+1] in wordDict and dp[0]
for j in range(i, n)])
for i in range(n)
][-1]
但要重复一遍:这不是Pythonic。最佳实践是让函数either改变参数(或
self
),or返回一个值,但不能同时返回两个值。此规则只有少数例外(例如.pop()
)
如果您对函数表达式感到满意而不是列表理解,则替代方案可以是使用
functools.reduce
:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
return reduce(lambda dp, i: [dp[j-i+1] or s[i:j+1] in wordDict and dp[0]
for j in range(i, n)],
range(n),
[True] + [False] * n)[0]