领英onsite新题

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

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

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

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

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

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

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

应该不需要吧

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

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

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

1. class Solution {
   
2.         Map<String, String> dict;
   
3. 
   
4.         public List<String> replaceString (String s1, List<String> s2, List<String> s3) {
   
5.                 dict = new HashMap<String, String>();
   
6.                 for (int i=0; i<s2.size(); i++) {
   
7.                         dict.put(s2.get(i), s3.get(i));
   
8.                 }
   
9.                
   
10.                 List<List<String>> dp = new LinkedList<List<String>>();
    
11.                 dp.add(new LinkedList<String>());
    
12.                 dp.get(0).add("");
    
13.                
    
14.                 for (int r=0; r<s1.length(); r++) {
    
15.                         dp.add(new LinkedList<String>());
    
16.                         for (int l=0; l<=r; l++) {
    
17.                                 String key = s1.substring(l, r+1);
    
18.                                 if (dict.containsKey(key)) {
    
19.                                         String suffix = dict.get(key);
    
20.                                         List<String> prefixs = dp.get(l);
    
21.                                         for (String prefix: prefixs) {
    
22.                                                 dp.get(r+1).add(prefix + suffix);
    
23.                                         }
    
24.                                 }
    
25.                         }
    
26.                         if (dp.get(r+1).size() == 0) {
    
27.                                 List<String> prefixs = dp.get(r);
    
28.                                 for (String prefix: prefixs) {
    
29.                                         dp.get(r+1).add(prefix + s1.charAt(r));
    
30.                                 }
    
31.                         }
    
32.                 }
    
33. 
    
34.                 return dp.get(s1.length());
    
35.         }
    
36. }

复制代码

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

1. class Solution{
   
2.         vector<string>ReplaceStr(string S, vector<string>candidate, vector<string>target){
   
3.         vector<string>res;
   
4.         unordered_map<string,string>R;
   
5.         for(int I = 0; I < candidate.size(); i++){
   
6.                 R[candidate[i]] = target[i];
   
7.         }
   
8.         string cur = “”;
   
9.         DFS(0,cur,S,R,res);
   
10.         return res;
    
11. 
    
12.         }
    
13.         void DFS(int index, string & cur, string& S, unordered_map<string,string>&R, vector<string>&res){
    
14.         if(index == S.length()){
    
15.                 res.push_back(cur);
    
16.                 return;       
    
17.         }
    
18.         bool canReplace = false;
    
19.         for( auto it: R){
    
20.                 if(index + it.first.length()-1 >= n)
    
21.                         continue;
    
22.                 string str = S.substr(index,it.first.length());
    
23.                 if(str == it.first){
    
24.                         canReplace = true;
    
25.                         DFS(index + it.first.length(), cur+it.second,S,R,res);
    
26.                 }
    
27.         }
    
28.         if(!canReplace)
    
29.                 DFS(index+1,cur+S[index],S,R,res);
    
30.         }
    
31. };

复制代码

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

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

say543 发表于 2018-1-12 15:53
我想memo 大概就是 pair 的substring 记录可能的substring 取代 这样吧 ？还是有更好的方法

我想了一想，你说的应该是对的，就是dfs return 一个string， 比如 dsf(i,j,R,S,res,dpMemo)，
用dfs往下走完了backtrack的时候记录一想s[i]到s[j]可以替换成什么string，下次再回溯到ij 的时候就不用再跑一遍了

楼主求问timeline