刪除字符串中所有子字符串的出現

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; 
}