删除字符串中所有子字符串的出现

Question

给定字符串S和一组n子字符串。从S中删除那些n子串的所有实例，以便S具有最小长度并输出此最小长度。

实施例1

S = ccdaabcdbb 
n = 2 
substrings = ab, cd 

输出

2 

说明：

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

实施例2

S = abcd 
n = 2 
substrings = ab,bcd 

输出

1 

我该如何解决这个问题？

Answer 1

一个简单的Brute-force search的算法是：

• 对于每个子串，尝试各种可能的方法来从字符串，然后递归删除它。

在Pseudocode：

def min_final_length (input, substrings): 
    best = len(input) 
    for substr in substrings: 
     beg = 0 
     // find all occurrences of substr in input and recurse 
     while (found = find_substring(input, substr, from=beg)): 
      input_without_substr = input[0:found]+input[found+len(substr):len(input)] 
      best = min(best, min_final_length(input_without_substr,substrings)) 
      beg = found+1 
    return best 

让复杂性是F(S,n,l)其中S是input字符串的长度，n是该集合的基数substrings和l是“特征长度”的子串。然后

F(S,n,l) ~ n * (S * l + F(S-l,n,l)) 

看起来最多是O(S^2*n*l)。

Answer 2

如果你是为了原始表现而且你的字符串非常大，你可以做得比蛮力更好。使用后缀trie（例如Ukkonnen trie）来存储您的字符串。然后找到每个子字符串（我们在O（m）时间完成的，m是子字符串长度），并将偏移量和长度存储在数组中。 然后使用偏移量和长度信息通过\ 0（在C中）或另一个占位符字符填充这些区域来实际删除子字符串。通过计算所有非空字符，您将获得最小字符串长度。

这将会处理重叠的子串，例如，说你的字符串是“abcd”，并且你有两个子字符串“ab”和“abcd”。

Answer 3

下列溶液将具有复杂度O（m * n个），其中m = LEN（S），n是我解决它使用字典树+ DP子

def foo(S, sub): 
    i = 0 
    while i < len(S): 
     for e in sub: 
      if S[i:].startswith(e): 
       S = S[:i] + S[i+len(e):] 
       i -= 1 
       break 
     else: i += 1 
    return S, i 

Answer 4

的数量。
首先在子树中插入你的子串。然后定义dp的状态是一些字符串，遍历该字符串并将每个i（对于i = 0 .. s.length（））作为某个子字符串的开始。让j = i并增加j，只要你在trie中有一个后缀（这肯定会让你至少有一个子字符串，如果你在一些子字符串之间有共同的后缀，比如“abce”和“abdd” ），每遇到一个子字符串的结尾，就解决新的子问题，并找到所有子字符串缩减之间的最小值。

这是我的代码。不要担心代码的长度。只要阅读解析函数并忘记路径，我将它包括在内以打印形成的字符串。

struct node{ 
    node* c[26]; 
    bool str_end; 
    node(){ 
     for(int i= 0;i<26;i++){ 
      c[i]=NULL; 
     } 
     str_end= false; 
    } 
}; 
class Trie{ 
public: 
    node* root; 
    Trie(){ 
     root = new node(); 
    } 
    ~Trie(){ 
     delete root; 
    } 
}; 
class Solution{ 
public: 
    typedef pair<int,int>ii; 
    string get_str(string& s,map<string,ii>&path){ 
     if(!path.count(s)){ 
      return s; 
     } 
     int i= path[s].first; 
     int j= path[s].second; 
     string new_str =(s.substr(0,i)+s.substr(j+1)); 
     return get_str(new_str,path); 
    } 
    int solve(string& s,Trie* &t, map<string,int>&dp,map<string,ii>&path){ 
     if(dp.count(s)){ 
      return dp[s]; 
     } 
     int mn= (int)s.length(); 
     for(int i =0;i<s.length();i++){ 
      string left = s.substr(0,i); 
      node* cur = t->root->c[s[i]-97]; 
      int j=i; 
      while(j<s.length()&&cur!=NULL){ 
       if(cur->str_end){ 
        string new_str =left+s.substr(j+1); 
        int ret= solve(new_str,t,dp,path); 
        if(ret<mn){ 
         path[s]={i,j}; 
        } 
       } 
       cur = cur->c[s[++j]-97]; 
      } 
     } 
     return dp[s]=mn; 
    } 
    string removeSubstrings(vector<string>& substrs, string s){ 
     map<string,ii>path; 
     map<string,int>dp; 
     Trie*t = new Trie(); 
     for(int i =0;i<substrs.size();i++){ 
      node* cur = t->root; 
      for(int j=0;j<substrs[i].length();j++){ 
       if(cur->c[substrs[i][j]-97]==NULL){ 
        cur->c[substrs[i][j]-97]= new node(); 
       } 
       cur = cur->c[substrs[i][j]-97]; 
       if(j==substrs[i].length()-1){ 
        cur->str_end= true; 
       } 
      } 
     } 
     solve(s,t,dp,path); 
     return get_str(s, path); 
    } 
}; 

int main(){ 
    vector<string>substrs; 
    substrs.push_back("ab"); 
    substrs.push_back("cd"); 
    Solution s; 
    cout << s.removeSubstrings(substrs,"ccdaabcdbb")<<endl; 
    return 0; 
}