求大牛指教，字符串分割的DP做法！ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求大牛指教，字符串分割的DP做法！

求大牛指教，字符串分割的DP做法！# JobHunting - 待字闺中

e*s2013-01-22 08:01

1 楼

一个连续没空格字符串，一个字典，怎样知道最少单词的分割方法？
http://thenoisychannel.com/2011/08/08/retiring-a-great-intervie
这是一个很好的POST，但是没有提供DP的方法。不知道这个递归的memorization算不算
DP？
多谢了！
方法定义
String segmentString(String s, Set dict)
例如
"applepie" -> "apple pie" 当然字典里面没有 "applepie" 这个字咯

p*22013-01-22 08:01

2 楼

要求只是求单词的数目，还是把分割单词都给出来呢？

e*s2013-01-22 08:01

3 楼

二爷，是要把分割的单词返回到一个字符串中，方法定义是
String segmentString(String s, Set dict)

【在 p*****2 的大作中提到】

: 要求只是求单词的数目，还是把分割单词都给出来呢？

e*s2013-01-22 08:01

4 楼

下面是我想到的，不知道对不对。
public static String segmentStringDP(String s, Set dict){
if(dict.contains(s)) return s;

int len = s.length();
int[] dp = new int[len];

for(int i = 0; i < len; i++)
{
for(int j = i; j < len; j++)
{
if(dict.contains(s.substring(i, j + 1)))
{
if(i == 0 || dp[i - 1] > 0)
dp[j] = Math.max(dp[j], j - i + 1);
}
}
}

if(dp[len -1] == 0)
return null;

StringBuilder sb = new StringBuilder();
int i = len - 1;
while(i >= 0)
{
sb.insert(0, s.substring(i - dp[i] + 1, i + 1) + " ");
i -= dp[i];
}
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}

p*22013-01-22 08:01

5 楼

dp+backtrack吧。

【在 e***s 的大作中提到】

: 二爷，是要把分割的单词返回到一个字符串中，方法定义是
: String segmentString(String s, Set dict)

w*o2013-01-22 08:01

6 楼

这样行不行？只能找到最少的个数，加个数组，稍改一下就能找到如何分割。
int n = s.length();
int[] dp = new int[n+1];
Arrays.fill(dp, 1000000);
dp[0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = i-1; j >= 0; j--) {
if(dict.contains(s.substring(j, i)))
dp[i] = Math.min(dp[i], dp[j]+1);
}
}
if(dp[n] > n)
System.out.println(“Not valid”);
else
System.out.println(“” + dp[n]);

p*22013-01-22 08:01

7 楼

def segmentString(s:String, dict:Set[String]):String={
val len=s.length()
val dp=Array.ofDim[Int](len+1,2)

(0 until len).reverse.foreach{i=>
(i+1 to len).foreach{j=>
if(dict.contains(s.substring(i,j)) &&
(j==len || dp(j)(0)>0) && (dp(i)(0)==0 || dp(j)(0)+1{
dp(i)(0)=dp(j)(0)+1
dp(i)(1)=j
}
}
}

var ab=ArrayBuffer[String]()
if(dp(0)(0)>0)
{
var i=0
while(i!=len)
{
ab+=s.substring(i,dp(i)(1))
i=dp(i)(1)
}
}
ab.mkString(" ")
}

d*g2013-01-22 08:01

8 楼

你不会面的同一家吧
http://stackoverflow.com/questions/3466972/how-to-split-a-strin

【在 e***s 的大作中提到】

: 一个连续没空格字符串，一个字典，怎样知道最少单词的分割方法？
: http://thenoisychannel.com/2011/08/08/retiring-a-great-intervie
: 这是一个很好的POST，但是没有提供DP的方法。不知道这个递归的memorization算不算
: DP？
: 多谢了！
: 方法定义
: String segmentString(String s, Set dict)
: 例如
: "applepie" -> "apple pie" 当然字典里面没有 "applepie" 这个字咯

l*a2013-01-22 08:01

9 楼

感觉上时间空间都可以再优化

+1
【在 p*****2 的大作中提到】

: def segmentString(s:String, dict:Set[String]):String={
: val len=s.length()
: val dp=Array.ofDim[Int](len+1,2)
:
: (0 until len).reverse.foreach{i=>
: (i+1 to len).foreach{j=>
: if(dict.contains(s.substring(i,j)) &&
: (j==len || dp(j)(0)>0) && (dp(i)(0)==0 || dp(j)(0)+1: {
: dp(i)(0)=dp(j)(0)+1

l*a2013-01-22 08:01

10 楼

从前往后做两层循环太费时间了吧？
是不是丛后面做更好？不构成单词的那些直接就无视了

【在 e***s 的大作中提到】

: 下面是我想到的，不知道对不对。
: public static String segmentStringDP(String s, Set dict){
: if(dict.contains(s)) return s;
:
: int len = s.length();
: int[] dp = new int[len];
:
: for(int i = 0; i < len; i++)
: {
: for(int j = i; j < len; j++)

e*s2013-01-22 08:01

11 楼

没有，我面经上看到的而已

【在 d********g 的大作中提到】

: 你不会面的同一家吧
: http://stackoverflow.com/questions/3466972/how-to-split-a-strin

e*s2013-01-22 08:01

12 楼

二爷您这是ruby还是python？看不懂，能不能搞个JAVA或C++版本看看？

+1
【在 p*****2 的大作中提到】

e*s2013-01-22 08:01

13 楼

对不起，我找到反例了，我的做法不正确。
"abcdef" Dictionary： {"abcde","f","ab","cd","ef"}
正确应该返回 "abcde f", 但是下面代码会返回 "ab cd ef" (不是最少单词数）;

【在 e***s 的大作中提到】

O*i2013-01-22 08:01

14 楼

这题在CAIWU的G面经也有？
和一个老美。先上来DP问题。说给一个字符串，是通过一些单词没有空格隔开的。让我
如果把他们分成最少的单词数。用了DP做出来。不过不知道他听懂没有。然后让设计一
个数据结构，使得一个人输入几个字母以后，会弹出来推荐的词。我用了prefix　tree
。然后他问怎么能最小化打字。我就说可以根据概率来弹出后面3个的推荐，然后一次
继续。然后在这个上面纠缠了很多，然后考虑了很多情况。然后算了一下期望可以减少
的打字数。

【在 e***s 的大作中提到】

e*s2013-01-22 08:01

15 楼

是的啊，我就是在那看到，发现自己做不出来的。
主要是“分成最少单词数”这一点，不知道该怎么DP。

tree

【在 O******i 的大作中提到】

: 这题在CAIWU的G面经也有？
: 和一个老美。先上来DP问题。说给一个字符串，是通过一些单词没有空格隔开的。让我
: 如果把他们分成最少的单词数。用了DP做出来。不过不知道他听懂没有。然后让设计一
: 个数据结构，使得一个人输入几个字母以后，会弹出来推荐的词。我用了prefix　tree
: 。然后他问怎么能最小化打字。我就说可以根据概率来弹出后面3个的推荐，然后一次
: 继续。然后在这个上面纠缠了很多，然后考虑了很多情况。然后算了一下期望可以减少
: 的打字数。

p*22013-01-22 08:01

16 楼

我试了一下我的代码，返回了
abcde f

【在 e***s 的大作中提到】

: 对不起，我找到反例了，我的做法不正确。
: "abcdef" Dictionary： {"abcde","f","ab","cd","ef"}
: 正确应该返回 "abcde f", 但是下面代码会返回 "ab cd ef" (不是最少单词数）;

p*22013-01-22 08:01

17 楼

scala的，跟java差不多吧。

【在 e***s 的大作中提到】

: 二爷您这是ruby还是python？看不懂，能不能搞个JAVA或C++版本看看？
:
: +1

p*22013-01-22 08:01

18 楼

我把思路写在博客了，你看看吧。
http://blog.sina.com.cn/s/blog_b9285de20101hrg7.html

【在 e***s 的大作中提到】

: 是的啊，我就是在那看到，发现自己做不出来的。
: 主要是“分成最少单词数”这一点，不知道该怎么DP。
:
: tree

e*s2013-01-22 08:01

19 楼

多谢二爷，看了您的“我的算法路”，羡慕，佩服。

【在 p*****2 的大作中提到】

:
: 我把思路写在博客了，你看看吧。
: http://blog.sina.com.cn/s/blog_b9285de20101hrg7.html

g*n2013-01-22 08:01

20 楼

跟风，做一个类C++ 的version.
typedef struct
{
bool can;
int mincount;
int endind;
} solelem;
if (s==null || s.len ==0 ) throw invalidinput;
soelem solutions[s.len] = {false, infty, -1};
for (startind=s.len-1; startind >=0; startind--)
{
if (dict.contains(s.substr(startind)))
{
sol[startind] = {true, 1, s.len-1};
}
else
{
mincount = infty;
for (i=startind; i<=s.len-2; i++)
{
if (dict.contains(s.substr(startind, i)))
{
if (sol[i+1].can)
{
if (sol[i+1].count +1 < mincount)
{
mincount = sol[i+1].count+1;
endind = i;
}
}
}
if (mincount == infty {sol[startind] = false/infty/-1;}
else
sol[startind] = {true, mincount, endind};
}
}
if (solutions[startind].can == false) throw "impossibe";
startind = 0;
while(startind < s.len)
{
result.append(s.substr(startind, solutions[startind].endind) + " "); //
append to result string
startind = solutions[startind].endind + 1;
}
return result;