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

Question

给定一个字符串S和一组n子串。从n中删除那些S子串的每个实例，使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中）或其他占位符字符填充这些区域来实际删除子字符串。通过计算所有非Null字符，您将获得字符串的最小长度。

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

Answer 3

以下解决方案将具有O（m * n）的复杂度，其中m = len（S）并且n是子串的数量

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

我用trie + dp解决了它。 首先在trie中插入子串。然后定义dp的状态是一些字符串，遍历该字符串并考虑每个i（对于i = 0 .. s.length（））作为某个子字符串的开头。只要你在trie中有一个后缀（这肯定会让你至少有一个子串，并且如果你在某个子串之间有一个共同的后缀，例如“abce”和“abdd”，则j = i并增加j） ），每当遇到一些子串的结束时，去解决新的子问题并找到所有子串减少之间的最小值。

这是我的代码。不要担心代码的长度。只需阅读解决功能并忘记路径，我将其包含在内，以打印形成的字符串。

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