Remove Substrings

• Lintcode : 624 / Leetcode :
• Level : Medium

Problem

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.

Example
Example 1:

Input:
"ccdaabcdbb"
["ab","cd"]
Output:
2
Explanation: 
ccdaabcdbb -> ccdacdbb -> cabb -> cb (length = 2)
Example 2:

Input:
"abcabd"
["ab","abcd"]
Output:
0
Explanation: 
abcabd -> abcd -> "" (length = 0)

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O()
space: O()

Answer

class Solution {
public:
    int minLength(string &s, unordered_set<string> &dict) {
        queue<string> q;
        unordered_set<string> repeat;
        q.push(s);
        repeat.insert(s);
        int minLen = s.length();
        while (!q.empty()) {
            string str = q.front(); q.pop();
            for (auto d : dict) {
                int index = str.find(d);
                while (index != -1) {
                    int len = d.size();
                    string newStr = str.substr(0, index) + str.substr(index + len, str.size() - len - index);
                    if (repeat.find(newStr) == repeat.end()) {
                        minLen = min(minLen, (int)newStr.size());
                        q.push(newStr);
                        repeat.insert(newStr);
                    }
                    // 嘗試不同組合
                    index = str.find(d, index + 1);
                }
            }
        }
        return minLen;
    }
};

/*
不同的組合可以有不同的答案，因此不能照順序消除
"abcabd"
["ab","abcd"]
Output
2
Expected
0
*/

tags: BFS

​