[算法] Remove Substrings

Question
Remove Substrings

Question Description

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.

Language
Python 3

Data structure description
""" @param: s: a string @param: dict: a set of n substrings @return: the minimum length """

Solution
class Solution: def minLength(self, s, dict): queue = collections.deque([s]) minLen = len(s) has = set([s]) while queue: tmp = queue.popleft() for seq in dict: index = tmp.find(seq) while index != -1: new_s = tmp[0: index] + tmp[index+len(seq):] if new_s not in has: has.add(new_s) queue.append(new_s) if len(new_s) < minLen: minLen = len(new_s) index = tmp.find(seq, index+1) return minLen

Reference Link
https://www.lintcode.com/problem/remove-substrings/description