K*****k
发帖数: 430 | 1 说给一个字符串，是通过一些单词没有空格隔开的。让我如果把他们分成最少的单词数
，用了DP做出来。
疑问：
1)没有空格隔开，是假定有个字典可以查询一个子串是否是单词么？
2)如果有多种分法，需要总次数最少？
3)感觉像硬币找零个数最少那题，可能无法用贪心法做，必须用动态规划？ |
l*******b
发帖数: 2586 | 2 有点像硬币找零，感觉
【在 K*****k 的大作中提到】
: 说给一个字符串，是通过一些单词没有空格隔开的。让我如果把他们分成最少的单词数
: ，用了DP做出来。
: 疑问：
: 1)没有空格隔开，是假定有个字典可以查询一个子串是否是单词么？
: 2)如果有多种分法，需要总次数最少？
: 3)感觉像硬币找零个数最少那题，可能无法用贪心法做，必须用动态规划？
|
p*****2
发帖数: 21240 | 3
1. yes
2. 总单词数最少
3. 是
【在 K*****k 的大作中提到】
: 说给一个字符串，是通过一些单词没有空格隔开的。让我如果把他们分成最少的单词数
: ，用了DP做出来。
: 疑问：
: 1)没有空格隔开，是假定有个字典可以查询一个子串是否是单词么？
: 2)如果有多种分法，需要总次数最少？
: 3)感觉像硬币找零个数最少那题，可能无法用贪心法做，必须用动态规划？
|
j*****y
发帖数: 1071 | 4 比如 check out 组成 checkout. 但是这个 checkout本身也是一个单词，所以
组成 checkout的这个字符串的最少单词数是 1 ?
【在 K*****k 的大作中提到】
: 说给一个字符串，是通过一些单词没有空格隔开的。让我如果把他们分成最少的单词数
: ，用了DP做出来。
: 疑问：
: 1)没有空格隔开，是假定有个字典可以查询一个子串是否是单词么？
: 2)如果有多种分法，需要总次数最少？
: 3)感觉像硬币找零个数最少那题，可能无法用贪心法做，必须用动态规划？
|
p*****2
发帖数: 21240 | 5
是。
【在 j*****y 的大作中提到】
: 比如 check out 组成 checkout. 但是这个 checkout本身也是一个单词，所以
: 组成 checkout的这个字符串的最少单词数是 1 ?
|
p*****2
发帖数: 21240 | 6 require 'set'
$dict=Set.new ['check','out','checkout']
def indict?(word)
$dict.include? word
end
def min_words(str)
n=str.length
dp=[-1]*(n+1)
dp[n]=0
(n-1).downto(0).each do |i|
min=-1
(1..n-i).each do |j|
if indict?(str[i,j]) && dp[i+j]>=0 && (min==-1 || dp[i+j]+1
min=dp[i+j]+1
end
end
dp[i]=min
end
dp[0]
end
p min_words('checkout') |
l*****a
发帖数: 14598 | 7 面试最忌讳让面世官无法理解
即使你的答案是对的
【在 p*****2 的大作中提到】
: require 'set'
: $dict=Set.new ['check','out','checkout']
: def indict?(word)
: $dict.include? word
: end
: def min_words(str)
: n=str.length
: dp=[-1]*(n+1)
: dp[n]=0
: (n-1).downto(0).each do |i|
|
t****a
发帖数: 1212 | 8 二爷写的这是ruby的code吧，漂亮。
【在 p*****2 的大作中提到】
: require 'set'
: $dict=Set.new ['check','out','checkout']
: def indict?(word)
: $dict.include? word
: end
: def min_words(str)
: n=str.length
: dp=[-1]*(n+1)
: dp[n]=0
: (n-1).downto(0).each do |i|
|
l*****a
发帖数: 14598 | 9 问题是遇上不懂的面世官
再漂亮也。。。
【在 t****a 的大作中提到】
: 二爷写的这是ruby的code吧，漂亮。
|
p*****2
发帖数: 21240 | 10
哇。多谢。我正好这个Chrismas没事干，就学了学。
【在 t****a 的大作中提到】
: 二爷写的这是ruby的code吧，漂亮。
|
|
|
p*****2
发帖数: 21240 | 11
感觉这才是好玩的地方。
【在 l*****a 的大作中提到】
: 面试最忌讳让面世官无法理解
: 即使你的答案是对的
|
K*****k
发帖数: 430 | 12 二爷的方法看不懂，郁闷。
能否把思路，主要是动态规划的递推方程给详细讲解一下？
动态规划估计不多刷题很难提高，另外也要有很强的bottom up的题感才行。 |
K*****k
发帖数: 430 | |
g*********e
发帖数: 14401 | |
p*****2
发帖数: 21240 | 15
这个没法收录，因为需要字典。
就是你从某个位置往后找
比如str[i,j]是一个单词那么结果就是dp[j+1]+1, 找所有的最小的那个就可以了。
【在 K*****k 的大作中提到】
: 这题leetcode有没有收录？
|
K*****k
发帖数: 430 | 16 我自己后来想了下，应该和二爷的思路大体一致，只不过二爷好像是从尾部倒着来，我
的是从头部顺着来。
二爷能否看看对不对。
假如char str[0 .. n - 1]是输入字符串
定义int dp[0 .. n - 1]，全部初始化为0
dp[j]表示str[0 .. j]的最小的划分词数，先计算出dp[0]来
求dp[j + 1], 就是
1) 如果str[0 .. j + 1]在字典中，直接设dp[j + 1] = 1
2) 遍历1 <= k <= j + 1, 如果str[k .. j + 1]在字典中且dp[k - 1]大于0,把最小的
那个dp[k - 1]加上1放到dp[j + 1]中
最后的结果就是返回dp[n - 1], 如果值为0表示无法分词。
【在 p*****2 的大作中提到】
:
: 这个没法收录，因为需要字典。
: 就是你从某个位置往后找
: 比如str[i,j]是一个单词那么结果就是dp[j+1]+1, 找所有的最小的那个就可以了。
|
s********l
发帖数: 998 | 17 严重同意！！！
【在 l*****a 的大作中提到】
: 面试最忌讳让面世官无法理解
: 即使你的答案是对的
|
s********l
发帖数: 998 | 18 我提议 这个论坛上 禁止用ruby! :P
【在 l*****a 的大作中提到】
: 问题是遇上不懂的面世官
: 再漂亮也。。。
|
b*****n
发帖数: 482 | 19 dp[k] = min(dp[i]+1 | i=[0, k-1], a[i+1]..a[k] is a valid word)
init with dp[0]=0, and string starts from a[1] for convenience
【在 K*****k 的大作中提到】
: 我自己后来想了下，应该和二爷的思路大体一致，只不过二爷好像是从尾部倒着来，我
: 的是从头部顺着来。
: 二爷能否看看对不对。
: 假如char str[0 .. n - 1]是输入字符串
: 定义int dp[0 .. n - 1]，全部初始化为0
: dp[j]表示str[0 .. j]的最小的划分词数，先计算出dp[0]来
: 求dp[j + 1], 就是
: 1) 如果str[0 .. j + 1]在字典中，直接设dp[j + 1] = 1
: 2) 遍历1 <= k <= j + 1, 如果str[k .. j + 1]在字典中且dp[k - 1]大于0,把最小的
: 那个dp[k - 1]加上1放到dp[j + 1]中
|
p*****2
发帖数: 21240 | 20
我一般都是从后往前的思路，如果recursive就是从前往后。这题你这么搞应该可以吧
，不过我脑子真不愿意这么想了。
【在 K*****k 的大作中提到】
: 我自己后来想了下，应该和二爷的思路大体一致，只不过二爷好像是从尾部倒着来，我
: 的是从头部顺着来。
: 二爷能否看看对不对。
: 假如char str[0 .. n - 1]是输入字符串
: 定义int dp[0 .. n - 1]，全部初始化为0
: dp[j]表示str[0 .. j]的最小的划分词数，先计算出dp[0]来
: 求dp[j + 1], 就是
: 1) 如果str[0 .. j + 1]在字典中，直接设dp[j + 1] = 1
: 2) 遍历1 <= k <= j + 1, 如果str[k .. j + 1]在字典中且dp[k - 1]大于0,把最小的
: 那个dp[k - 1]加上1放到dp[j + 1]中
|
|
|
m******s
发帖数: 165 | 21 好久不刷题了，写一个玩玩，估计多半哪儿有小错。。。
int getmin(string str, vector dic)
{
int n = str.size();
const int INF = n + 1;
vector dp(n + 1, INF);
dp[0] = 0;
for (int i = 0; i < n; ++i)
if (dp[i] < INF)
for (int j = 0; j < dic.size(); ++j)
if (str.substr(i, dic[j].size()) == dic[j])
dp[i + dic[j].size()] = min(dp[i + dic[j].size()], dp[i] + 1);
return dp[n] < INF ? dp[n] : -1;
}
【在 K*****k 的大作中提到】
: 说给一个字符串，是通过一些单词没有空格隔开的。让我如果把他们分成最少的单词数
: ，用了DP做出来。
: 疑问：
: 1)没有空格隔开，是假定有个字典可以查询一个子串是否是单词么？
: 2)如果有多种分法，需要总次数最少？
: 3)感觉像硬币找零个数最少那题，可能无法用贪心法做，必须用动态规划？
|
b*********h
发帖数: 103 | 22 用 trie 来做时间是 O(N*L) 的，L 是最长单词长度
f(i+j) = min{f(i)} + 1, 其中 s(i+1:j) 能查到
用 f(i) 去刷 f(i+j)，就是从第 i+1 开始在 trie 里走，走到 j 发现是单词就刷新
f(i+j)，走不下去了就换 f(i+1)
有挺多这种题在 OJ 里的，读字典自己建树 |
b*****n
发帖数: 482 | 23 怎么保证最少单词呢？
新
【在 b*********h 的大作中提到】
: 用 trie 来做时间是 O(N*L) 的，L 是最长单词长度
: f(i+j) = min{f(i)} + 1, 其中 s(i+1:j) 能查到
: 用 f(i) 去刷 f(i+j)，就是从第 i+1 开始在 trie 里走，走到 j 发现是单词就刷新
: f(i+j)，走不下去了就换 f(i+1)
: 有挺多这种题在 OJ 里的，读字典自己建树
|
l*****a
发帖数: 14598 | 24 min=Integer.MAX_VALUE;
然后update min
【在 b*****n 的大作中提到】
: 怎么保证最少单词呢？
:
: 新
|
b*****n
发帖数: 482 | 25 oh, 那还是dp, 我还以为直接在trie里走就行了呢，呵呵:)
【在 l*****a 的大作中提到】
: min=Integer.MAX_VALUE;
: 然后update min
|
K*****k
发帖数: 430 | 26 动态规划是不是有两种刷法？
一种就是你这样在当前位置就先刷后面位置的。
另外一种是从当前位置往前找，用前面的位置刷当前的位置。
新
【在 b*********h 的大作中提到】
: 用 trie 来做时间是 O(N*L) 的，L 是最长单词长度
: f(i+j) = min{f(i)} + 1, 其中 s(i+1:j) 能查到
: 用 f(i) 去刷 f(i+j)，就是从第 i+1 开始在 trie 里走，走到 j 发现是单词就刷新
: f(i+j)，走不下去了就换 f(i+1)
: 有挺多这种题在 OJ 里的，读字典自己建树
|
K*****k
发帖数: 430 | 27 Ruby里头是不是str[i,j]表示i位置开始，长度为j的子串？这里j是长度而不是下标？
另外应该是dp[j+i]+1？
还有如果知道最长单词是L，应该可以限制j的范围，把复杂度从O(N^2）降到O(N*L)？
【在 p*****2 的大作中提到】
:
: 我一般都是从后往前的思路，如果recursive就是从前往后。这题你这么搞应该可以吧
: ，不过我脑子真不愿意这么想了。
|
K*****k
发帖数: 430 | 28 为什么要用trie存单词呢？假如字典是哈希表，判断一个字符串是不是在字典不就是O(
1)?
新
【在 b*********h 的大作中提到】
: 用 trie 来做时间是 O(N*L) 的，L 是最长单词长度
: f(i+j) = min{f(i)} + 1, 其中 s(i+1:j) 能查到
: 用 f(i) 去刷 f(i+j)，就是从第 i+1 开始在 trie 里走，走到 j 发现是单词就刷新
: f(i+j)，走不下去了就换 f(i+1)
: 有挺多这种题在 OJ 里的，读字典自己建树
|
l*****a
发帖数: 14598 | 29 用trie可以提前退出
for example
a[0] a[1] in dic
a[0] a[1] a[2] a[3] in dic
if a[0] a[1] a[2] a[3] a[4] is not a path in trie,u don't need to start from
a[0] any more
O(
【在 K*****k 的大作中提到】
: 为什么要用trie存单词呢？假如字典是哈希表，判断一个字符串是不是在字典不就是O(
: 1)?
:
: 新
|
b*********h
发帖数: 103 | 30 对的
【在 K*****k 的大作中提到】
: 动态规划是不是有两种刷法？
: 一种就是你这样在当前位置就先刷后面位置的。
: 另外一种是从当前位置往前找，用前面的位置刷当前的位置。
:
: 新
|
|
|
b*********h
发帖数: 103 | 31 嗯 提前退出 而且不用每次都构建字符串 感觉常数会小
O(
【在 K*****k 的大作中提到】
: 为什么要用trie存单词呢？假如字典是哈希表，判断一个字符串是不是在字典不就是O(
: 1)?
:
: 新
|
p*****2
发帖数: 21240 | 32
嗯。是这样子的。
【在 K*****k 的大作中提到】
: Ruby里头是不是str[i,j]表示i位置开始，长度为j的子串？这里j是长度而不是下标？
: 另外应该是dp[j+i]+1？
: 还有如果知道最长单词是L，应该可以限制j的范围，把复杂度从O(N^2）降到O(N*L)？
|
c********t
发帖数: 5706 | 33 不一定非要用动态规划，从头开始recursion也可解
【在 K*****k 的大作中提到】
: 说给一个字符串，是通过一些单词没有空格隔开的。让我如果把他们分成最少的单词数
: ，用了DP做出来。
: 疑问：
: 1)没有空格隔开，是假定有个字典可以查询一个子串是否是单词么？
: 2)如果有多种分法，需要总次数最少？
: 3)感觉像硬币找零个数最少那题，可能无法用贪心法做，必须用动态规划？
|
