c******3
发帖数: 5 | 1 输入一个词典termDict.txt，每行一个单词，同时输入一个不含空格的字符串，例如：
ilovethisgame，输出包含空格的英文句子，例如I love this game。
要求：
1， 编码实现该函数，如果有多种可能输出，输出所有可能
2， 建议先考虑整体流程，再进行优化，若时间有限，可使用部分伪代码
3， 分析并讨论：如果有多种可能输出，如何选择最有可能的输出 | p*****2
发帖数: 21240 | 2 (defn word-break [str]
((fn dfs [str, p, res]
(if (= p (count str))
(println res)
(loop [end (inc p)]
(when (<= end (count str))
(let [word (subs str p end)]
(when (contains? dict word)
(dfs str end (conj res word)))
(recur (inc end)))))))
str 0 [])) | c******3
发帖数: 5 | 3 def y(l, r):
if(l>r):
return 1
if(a[l]>-1):
return a[l]
i=l
while i<=r:
if(s[l:i+1] in dict):
a[i]=y(i+1, r)
if(a[i]==1):
return 1
i+=1
return 0
f=open('termDict.txt')
dict=set()
for line in f:
dict.add(line.strip())
s='ilovethisgame'
a=len(s)*[-1]
y(0, len(s)-1)
k=0
c=[]
for i in range(len(a)):
if(a[i]==1):
c.append(s[k:i+1])
k=i+1
print c | f******n
发帖数: 53 | 4 如果是考虑多种组合，显然是DP算法。
构建dp[s.length][s.length]
根据dict设置dp[i][j] = 1 其中s[i...j]可以在dict中找到
dp每行会有多个1
根据ilovethisgame的静态算法如下
显示的a[i] 为每个word的第一个字母位置
void printpath (int a[13])
{
for (int i = 0; i < 13; i++)
printf("%d ", a[i]);
printf("n");
}
bool findAllPath(int dp[13][13], int a[13], int s, int e)
{
if (dp[s][e] == 1)
{
a[s]=1;
printpath(a);
return true;
}
int i = s;
bool found = false;
while (i <= e)
{
if (dp[s][i] == 1)
{
a[s]=1;
if (findAllPath(dp, a, i+1, e) == true)
found = true;
}
i++;
}
return found;
}
int _tmain(int argc, _TCHAR* argv[])
{
int dp[13][13];
for (int i = 0; i < 13; i++)
for (int j = 0; j < 13; j++)
dp[i][j]=0;
int a[13];
for (int i = 0; i < 13; i++)
a[i]=0;
dp[0][0] = 1;
dp[1][4] = 1;
dp[5][8] = 1;
dp[9][12] = 1;
findAllPath(dp, a, 0, 12);
return 0;
} | z*******h
发帖数: 346 | 5 你这个根本不是Dynamic Programming。你的dp table里的东西就没有被update. 你这
个还是brute force的 recursive solution.
其实这是个BFS or DFS可以解决的问题。
【在 f******n 的大作中提到】
: 如果是考虑多种组合，显然是DP算法。
: 构建dp[s.length][s.length]
: 根据dict设置dp[i][j] = 1 其中s[i...j]可以在dict中找到
: dp每行会有多个1
: 根据ilovethisgame的静态算法如下
: 显示的a[i] 为每个word的第一个字母位置
: void printpath (int a[13])
: {
: for (int i = 0; i < 13; i++)
: printf("%d ", a[i]);
| o*****n
发帖数: 189 | | w********s
发帖数: 1570 | 7 错，要记录下已知的break
awarehouseisawarehouse
awarehouse = aware house, a ware house, a warehouse
isawarehouse = is a warehouse, is a ware house
isawarehouse已知的break不需要在下次继续求。
【在 z*******h 的大作中提到】
: 你这个根本不是Dynamic Programming。你的dp table里的东西就没有被update. 你这
: 个还是brute force的 recursive solution.
: 其实这是个BFS or DFS可以解决的问题。
| z*******h
发帖数: 346 | 8 他的code中哪里记录下已知的break了？
【在 w********s 的大作中提到】
: 错，要记录下已知的break
: awarehouseisawarehouse
: awarehouse = aware house, a ware house, a warehouse
: isawarehouse = is a warehouse, is a ware house
: isawarehouse已知的break不需要在下次继续求。
| l**********a
发帖数: 181 | |
|
