问答

当前位置

请教关于dfs for 循环

  • Ta: 林湖龙

助教老师您好,
比如 word break ii https://www.jiuzhang.com/solution/word-break-ii/#tag-highlight-lang-python
或者 Palindrome Partitioning https://www.jiuzhang.com/solution/palindrome-partitioning/#tag-highlight-lang-python

请问为什么这两个题目只for 循环 划分终点
for i in range(1, len(s)):
prefix = s[:i]
而不像 word search https://www.jiuzhang.com/solution/word-search/#tag-highlight-lang-python 或者 combination sum https://www.jiuzhang.com/solution/combination-sum/#tag-highlight-lang-python
一样也要for 起点呢?
比如为什么不是
for i in range(startidx, len(s)):
for j in range(i+1, len(s)+1):
prefix = s[i:j]
dfs....
经常想不清楚要不要加上for循环,循环的是起点还是终点,希望老师解答,谢谢

2 个回复

2019-09-20 carry

这个要看具体的题意,有些题是对不同的起点进行循环DFS,有些是对终点进行循环,这个需要多练题。比如说单词拆分,肯定是对后面进行拆分,拿到一个单词他可以在这个单词不同地方拆分,而单词查找肯定要在开始的时候循环起点先。


2019-09-21 衡助教

嗯,你就这样理解吧。
如果dfs最后搜到的答案里,最开始的字母或者数字都是从第一位开始的,就只需要dfs结尾。(或者说,最终的答案为输入的split的集合)
如果答案里开头部分不同,就要两重for。(最后的答案,为输入的一个组合的集合)

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1