Удалить все вхождения подстрок из строки

Учитывая строку 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

Как мне решить эту проблему?

Источник

4 ответа

Простой алгоритм поиска методом грубой силы:

  • Для каждой подстроки попробуйте все возможные способы удалить ее из строки, а затем повторить.

В псевдокоде:

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),

Источник

Следующее решение будет иметь сложность 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
Источник

Я решил это с помощью trie+dp.
Сначала вставьте ваши подстроки в три. Затем определите состояние dp какой-либо строки, пройдитесь по этой строке и рассмотрите каждый i (для i =0 .. s.length()) как начало некоторой подстроки. пусть j=i и увеличивают j до тех пор, пока у вас есть суффикс в три (что определенно приведет вас к хотя бы одной подстроке и может быть больше, если у вас есть общий суффикс между некоторыми подстроками, например, "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;
}
Источник

Если вам нужна грубая производительность и ваша строка очень большая, вы можете добиться большего успеха, чем грубая сила. Используйте суффикс trie (например, Ukkonnen trie) для хранения вашей строки. Затем найдите каждую подстроку (которую мы сделали за время O(m), m - длина подстроки) и сохраните смещения для подстрок и длины в массиве. Затем используйте информацию о смещениях и длине, чтобы фактически удалить подстроки, заполнив эти области \0 (в C) или другим символом-заполнителем. Подсчитав все ненулевые символы, вы получите минимальную длину строки.

Это также будет обрабатывать перекрывающуюся подстроку, например, скажем, ваша строка "abcd", и у вас есть две подстроки "ab" и "abcd".

Источник
Другие вопросы по тегам