领英onsite新题

楼上洗衣机成精

octluck 发表于 2018-1-11 13:20
原来用work break II 的思路，结果没有写出来

恩，好思路。感觉确实是一类问题。谢谢楼主。

octluck

楼上洗衣机成精发表于 2018-1-11 13:30
恩，好思路。感觉确实是一类问题。谢谢楼主。

如果你写出来能贴一个吗？或者站内也行，多谢啦

say543

octluck 发表于 2018-1-11 13:07
这个我没问，应该没什么要求吧，但是不能替换的字母顺序不能变

需要考虑回朔吗ex : abb => acc => add if {b => c, cc=> dd} ?

octluck

say543 发表于 2018-1-11 15:08
需要考虑回朔吗ex : abb => acc => add if {b => c, cc=> dd} ?

应该不需要吧

楼上洗衣机成精

octluck 发表于 2018-1-11 13:42
如果你写出来能贴一个吗？或者站内也行，多谢啦

额，想了一晚上没想出来ｄｆｓ＋ｍｅｍ要怎么实现。感觉要保证所有应该被替换的ｓｕｂｓｔｒｉｎｇ都被替换好难。

想了个ＤＰ的解法，不知道对不对：

class Solution {
Map<String, String> dict;
public List<String> replaceString (String s1, List<String> s2, List<String> s3) {
dict = new HashMap<String, String>();
for (int i=0; i<s2.size(); i++) {
dict.put(s2.get(i), s3.get(i));
}
List<List<String>> dp = new LinkedList<List<String>>();
dp.add(new LinkedList<String>());
dp.get(0).add("");
for (int r=0; r<s1.length(); r++) {
dp.add(new LinkedList<String>());
for (int l=0; l<=r; l++) {
String key = s1.substring(l, r+1);
if (dict.containsKey(key)) {
String suffix = dict.get(key);
List<String> prefixs = dp.get(l);
for (String prefix: prefixs) {
dp.get(r+1).add(prefix + suffix);
}
}
}
if (dp.get(r+1).size() == 0) {
List<String> prefixs = dp.get(r);
for (String prefix: prefixs) {
dp.get(r+1).add(prefix + s1.charAt(r));
}
}
}
return dp.get(s1.length());
}
}

复制代码

bear3488

我试着写了一个DFS的，没有lz说的memo的。。。不知道对不对

class Solution{
vector<string>ReplaceStr(string S, vector<string>candidate, vector<string>target){
vector<string>res;
unordered_map<string,string>R;
for(int I = 0; I < candidate.size(); i++){
R[candidate[i]] = target[i];
}
string cur = “”;
DFS(0,cur,S,R,res);
return res;
}
void DFS(int index, string & cur, string& S, unordered_map<string,string>&R, vector<string>&res){
if(index == S.length()){
res.push_back(cur);
return;
}
bool canReplace = false;
for( auto it: R){
if(index + it.first.length()-1 >= n)
continue;
string str = S.substr(index,it.first.length());
if(str == it.first){
canReplace = true;
DFS(index + it.first.length(), cur+it.second,S,R,res);
}
}
if(!canReplace)
DFS(index+1,cur+S[index],S,R,res);
}
};

复制代码

补充内容 (2018-1-12 13:30):
贴上去发现tab的好奇怪。。。。将就看吧。。。。

say543

我想memo 大概就是[i,j] pair 的substring 记录可能的substring 取代这样吧？还是有更好的方法

bear3488

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

joyoox

楼主求问timeline

bingmo

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式