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)感觉像硬币找零个数最少那题,可能无法用贪心法做,必须用动态规划?
|