e***s
发帖数: 799 | 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*****2
发帖数: 21240 | 2 要求只是求单词的数目，还是把分割单词都给出来呢？ |
e***s
发帖数: 799 | 3 二爷，是要把分割的单词返回到一个字符串中，方法定义是
String segmentString(String s, Set dict)
【在 p*****2 的大作中提到】
: 要求只是求单词的数目，还是把分割单词都给出来呢？
|
e***s
发帖数: 799 | 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*****2
发帖数: 21240 | 5
dp+backtrack吧。
【在 e***s 的大作中提到】
: 二爷，是要把分割的单词返回到一个字符串中，方法定义是
: String segmentString(String s, Set dict)
|
w***o
发帖数: 109 | 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*****2
发帖数: 21240 | 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********g
发帖数: 10550 | 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*****a
发帖数: 14598 | 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*****a
发帖数: 14598 | 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***s
发帖数: 799 | |
e***s
发帖数: 799 | 12 二爷您这是ruby还是python？ 看不懂，能不能搞个JAVA或C++版本看看？
+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
|
e***s
发帖数: 799 | 13 对不起，我找到反例了，我的做法不正确。
"abcdef" Dictionary： {"abcde","f","ab","cd","ef"}
正确应该返回 "abcde f", 但是下面代码会返回 "ab cd ef" (不是最少单词数）;
【在 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++)
|
O******i
发帖数: 269 | 14 这题在CAIWU的G面经也有？
和一个老美。先上来DP问题。说给一个字符串，是通过一些单词没有空格隔开的。让我
如果把他们分成最少的单词数。用了DP做出来。不过不知道他听懂没有。然后让设计一
个数据结构，使得一个人输入几个字母以后，会弹出来推荐的词。我用了prefix tree
。然后他问怎么能最小化打字。我就说可以根据概率来弹出后面3个的推荐，然后一次
继续。然后在这个上面纠缠了很多，然后考虑了很多情况。然后算了一下期望可以减少
的打字数。
【在 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" 这个字咯
|
e***s
发帖数: 799 | 15 是的啊，我就是在那看到，发现自己做不出来的。
主要是“分成最少单词数”这一点，不知道该怎么DP。
tree
【在 O******i 的大作中提到】
: 这题在CAIWU的G面经也有？
: 和一个老美。先上来DP问题。说给一个字符串，是通过一些单词没有空格隔开的。让我
: 如果把他们分成最少的单词数。用了DP做出来。不过不知道他听懂没有。然后让设计一
: 个数据结构，使得一个人输入几个字母以后，会弹出来推荐的词。我用了prefix tree
: 。然后他问怎么能最小化打字。我就说可以根据概率来弹出后面3个的推荐，然后一次
: 继续。然后在这个上面纠缠了很多，然后考虑了很多情况。然后算了一下期望可以减少
: 的打字数。
|
p*****2
发帖数: 21240 | 16
我试了一下我的代码，返回了
abcde f
【在 e***s 的大作中提到】
: 对不起，我找到反例了，我的做法不正确。
: "abcdef" Dictionary： {"abcde","f","ab","cd","ef"}
: 正确应该返回 "abcde f", 但是下面代码会返回 "ab cd ef" (不是最少单词数）;
|
p*****2
发帖数: 21240 | 17
scala的，跟java差不多吧。
【在 e***s 的大作中提到】
: 二爷您这是ruby还是python？ 看不懂，能不能搞个JAVA或C++版本看看？
:
: +1
|
p*****2
发帖数: 21240 | 18
我把思路写在博客了，你看看吧。
http://blog.sina.com.cn/s/blog_b9285de20101hrg7.html
【在 e***s 的大作中提到】
: 是的啊，我就是在那看到，发现自己做不出来的。
: 主要是“分成最少单词数”这一点，不知道该怎么DP。
:
: tree
|
e***s
发帖数: 799 | 19 多谢二爷，看了您的“我的算法路”，羡慕，佩服。
【在 p*****2 的大作中提到】
:
: 我把思路写在博客了，你看看吧。
: http://blog.sina.com.cn/s/blog_b9285de20101hrg7.html
|
g*********n
发帖数: 43 | 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; |
