贡献一道题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

贡献一道题

贡献一道题# JobHunting - 待字闺中

r*d2012-11-27 08:11

1 楼

给定 bool isWord(string s)
create function to print all words based on a string
for example， input: this is desktop
output is: this is desk top
this is desktop
题好象从没见过，大家讨论一下

p*22012-11-27 08:11

2 楼

DP, DFS都行。

b*m2012-11-27 08:11

3 楼

Input里面未必要有空格吧？其实就是给定词典然后返回所有可能的单词？

r*d2012-11-27 08:11

4 楼

面试官给的例子没有空格，谁能简单写一下？

【在 b***m 的大作中提到】

: Input里面未必要有空格吧？其实就是给定词典然后返回所有可能的单词？

b*m2012-11-27 08:11

5 楼

参考8皇后backtrack的解法。

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

: 面试官给的例子没有空格，谁能简单写一下？

h*n2012-11-27 08:11

6 楼

写了一个，没测，楼主测测有问题告诉我
bool isWord(string s)
{
if(s=="this") return true;
if(s=="is") return true;
if(s=="desk") return true;
if(s=="top") return true;
if(s=="desktop") return true;
return false;
}
void Helper(string &inputS, int start, string &tmpStr, vector &res)
{
if(start == inputS.size())
{
//删除多余的空格
tmpStr.erase(tmpStr.end()-1);
res.push_back(tmpStr);
//补回来以便正确的backtracking
tmpStr.push_back(' ');
return;
}
int i;
string str;
for(i=start;i{
if(isWord(inputS.substr(start,i-start+1)))
{
tmpStr.append(inputS.substr(start,i-start+1));
tmpStr.push_back(' ');
Helper(inputS,i+1,tmpStr,res);
tmpStr.erase(tmpStr.end()-(i-start+2), tmpStr.end());
}
}
}
vector GetValidSentence(string inputS)
{
int size = inputS.size();
vector res;
string tmpStr="";
Helper(inputS, 0, tmpStr, res);
return res;
}

r*d2012-11-27 08:11

7 楼

简单改成C#测了一下，有bug
for example, input: thisisallsome
there are 24 output strings which is wrong
the output is like: this is allsome, this is is a some, this is all allsome

【在 h****n 的大作中提到】

: 写了一个，没测，楼主测测有问题告诉我
: bool isWord(string s)
: {
: if(s=="this") return true;
: if(s=="is") return true;
: if(s=="desk") return true;
: if(s=="top") return true;
: if(s=="desktop") return true;
: return false;
: }

h*n2012-11-27 08:11

8 楼

我测了一下，C++代码没有问题只有两个输出
this is all some , this is allsome
你怎么改的，把你代码贴上来看看

r*d2012-11-27 08:11

9 楼

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace ConsoleApplication1
{
class Program
{
static private bool isWord(string s)
{
switch (s)
{
case "this":
case "is":
case "a":
case "all":
case "some":
case "allsome":
return true;
}
return false;
}
static private LinkedList GetValidSentence(string inputS)
{
int size = inputS.Length;
LinkedList res = new LinkedList();
string tmpStr="";
Helper(inputS, 0, tmpStr, res);
return res;
}
static private void Helper(string inputS, int start, string tmpStr,
LinkedList res)
{
if (start == inputS.Length)
{
//删除多余的空格
tmpStr.Remove(tmpStr.Length-1);
res.AddLast(tmpStr);
//补回来以便正确的backtracking
tmpStr += ' ';
return;
}
int i, j;
string str;
for (i = start; i < inputS.Length; i++)
{
for (j = i; j < inputS.Length; j++)
{
if (isWord(inputS.Substring(i, j - i + 1)))
{
tmpStr += inputS.Substring(i, j - i + 1);
tmpStr += ' ';
Helper(inputS, j + 1, tmpStr, res);
tmpStr.Remove(tmpStr.Length - (j - i + 2), j - i + 2);
}
}
}
}
static void Main(string[] args)
{
LinkedList l = GetValidSentence("thisisallsome");
}
}
}

【在 h****n 的大作中提到】

: 我测了一下，C++代码没有问题只有两个输出
: this is all some , this is allsome
: 你怎么改的，把你代码贴上来看看

h*n2012-11-27 08:11

10 楼

呵呵，你改的是我之前的那个版本。。你改改我上面那个updated过得版本。。只有一
层for loop，之前想复杂了
另外需要注意的一个地方就是C#里面的string貌似是pass by value？如果是的话你得
加个ref之类的东西来变成pass by reference

C*U2012-11-27 08:11

11 楼

很像我面的一个题目
用dp就可以

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

: 给定 bool isWord(string s)
: create function to print all words based on a string
: for example， input: this is desktop
: output is: this is desk top
: this is desktop
: 题好象从没见过，大家讨论一下