A9 电面

A9 店棉，一道题：You are given a string S and a set of n substrings. You are supposed to remove every instance of those n substrings from S so that S is of the minimum length and output this minimum length. Eg:
S- ccdaabcdbb
n=2 - substrings-- (ab, cd)
Output: 2

Explanation:
ccdaabcdbb -> ccdacdbb -> cabb -> cb (length=2)

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

0, 0)">        }
    }
}


现在还没想到直接DP怎么做，好久没刷DP的题了，手真的有些生了。希望台湾小哥高抬贵手。能到下轮电面。


补充内容 (2016-12-9 03:24):
dp[i] =  dp[i - lengthOfSubstring]   if dict.cotain(s.substr(i - lengthOfSubstring)).

Otherwise
    dp[i] = dp[i - lengthOfSubstring] + lenOfSubstring

补充内容 (2016-12-9 03:31):
  If the length of substring in the set is not the same, just iterate in the set to check if that string is the same as the substring (i- lengthOfStr, lengthOfStr).

刚从面试的教室出来，就想到dp怎么做了，我这是肿么了，5555.这么好的机会感觉要被浪费了。赶紧给台湾小哥发了两份邮件。把我想法表达了一下。希望能起到哪怕一丁点的作用。台湾人民最可爱了。一定手下留情啊。

This code passed the test case:

1. class SolutionA9 {
   
2. public:
   
3.     int minLength(string s, set<string> dict) {
   
4.         if(dict.size() == 0)
   
5.             return s.size();
   
6.         //using dp[i] to store the min length at index i
   
7.         vector<int> dp(s.size(), INT_MAX);
   
8.         dp[0] = 0;
   
9.         vector<string> trace(s.size(), "");
   
10.         auto it = dict.begin();
    
11.         int len = (*it).size();
    
12.         for(int i = 0; i < s.size(); i++) {
    
13.             if(i < len - 1) {
    
14.                 trace[i] = s.substr(0, i + 1);
    
15.                 dp[i] = i + 1;
    
16.                 continue;
    
17.             }
    
18.             if(dict.count(s.substr(i - len + 1, len))) {
    
19.                 if(i - len >= 0) {
    
20.                     dp[i] = min(dp[i], dp[i - len]);
    
21.                     trace[i] = trace[i - len];
    
22.                 }
    
23.                 else {
    
24.                     dp[i] = 0;
    
25.                     trace[i] = "";
    
26.                 }
    
27.             }else {
    
28.                 if(i - len >= 0) {
    
29.                     dp[i] = min(dp[i], dp[i - len] + len);
    
30.                     trace[i] = trace[i - len] + s.substr(i - len + 1, len);
    
31.                 }else {
    
32.                     dp[i] = len;
    
33.                     trace[i] = s.substr(i - len + 1, len);
    
34.                 }
    
35.                
    
36.             }
    
37.             for(int j = i - 1; j >= 0; j--) {
    
38.                 string candidite = trace[j] + s.substr(j + 1, i - j);
    
39.                 int n = candidite.size();
    
40.                 if(n >= len && dict.count(candidite.substr(n - len, len)) && dp[j] < dp[i]) {
    
41.                     dp[i] = dp[j];
    
42.                     trace[i] = candidite.substr(0, n - len);
    
43.                 }else if(dp[j] + i - j  < dp[i]) {
    
44.                     dp[i] = dp[j] + i - j;
    
45.                     trace[i] = trace[j] + s.substr(j+1, i - j);
    
46.                 }
    
47.             }
    
48.         }
    
49.         return dp[s.size() - 1];
    
50.     }
    
51. };

复制代码

请问LZ投的是什么组啊？谢谢

螺丝苹果派 发表于 2016-12-9 05:50
请问LZ投的是什么组啊？谢谢

big data

楼主你好！ 今天我也收到了software engineer big data电面的e-mail。看了你的面经，感觉不会问到和big data相关的问题对吗？考的主要还是算法?

LZ 请问dict中的string长度都相等吗

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies