search

zhangyuanes / cpp-interviews-code

2 stars 0 forks source link

【2021-字节实习一面】1.字符串是否能由单词列表构成 #30

Open dai-pei opened 3 years ago

dai-pei commented 3 years ago

字符串 s ： ilovebytedance 单词列表 words[]： i,love,byte,bytedance 返回：true/false 思路：dp[i]表示s[0]...s[i]这个子串能否由单词列表构成 dp[i]=if_exists_in_wordlist(words[k])&&dp[i-words[k].length()]

zkm98 commented 3 years ago

dp[i] 代表的是s[i] .... s[n-1]是否是由单词列表构成，

if dp[i] == -1 dfs下去; else if dp[i] == 0 return dp[i-目前匹配的单词长度] = false; else return dp[i-目前匹配的单词长度] = true;

zkm98 commented 3 years ago

for i in 0--str.length: for j in 1--i: if str[j:i]为某个单词 && dp[i-j] dp[i] = true;break;

return dp[length]