由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 求大牛指教,字符串分割的DP做法!
相关主题
一道G家店面题问道google面试题
LinkedIn onsite一道题问个java hashcode的题
请教leetcode上的那道Word Break II,多谢!Exposed上一道string permutation的题
HackerRank find string..问个考古的题
专家们,find the longest common substring of two strings问一个facebook的电面
问两道google题做题做得很郁闷,求指点
一道面试题(integer to binary string)问一道A家的面试题
收到G家拒信,发面经发个Twitter的面试题
相关话题的讨论汇总
话题: dp话题: startind话题: string话题: len话题: int
进入JobHunting版参与讨论
1 (共1页)
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++)

相关主题
问两道google题问道google面试题
一道面试题(integer to binary string)问个java hashcode的题
收到G家拒信,发面经Exposed上一道string permutation的题
进入JobHunting版参与讨论
e***s
发帖数: 799
11
没有,我面经上看到的而已

【在 d********g 的大作中提到】
: 你不会面的同一家吧
: http://stackoverflow.com/questions/3466972/how-to-split-a-strin

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;
1 (共1页)
进入JobHunting版参与讨论
相关主题
发个Twitter的面试题专家们,find the longest common substring of two strings
50行code能解决addbinary 问题么问两道google题
好不容易写了个bug free, 可是被说会秒据, 帮看看一道面试题(integer to binary string)
ZigZag 又读不懂题了,求助!收到G家拒信,发面经
一道G家店面题问道google面试题
LinkedIn onsite一道题问个java hashcode的题
请教leetcode上的那道Word Break II,多谢!Exposed上一道string permutation的题
HackerRank find string..问个考古的题
相关话题的讨论汇总
话题: dp话题: startind话题: string话题: len话题: int