LeetCode刷题：301. Remove Invalid Parentheses （DFS算法设计和BFS算法设计）-白红宇

LeetCode刷题：301. Remove Invalid Parentheses （DFS算法设计和BFS算法设计）

阅读量：4040 次

发布时间：2019-05-24

本文共 3654 字，大约阅读时间需要 12 分钟。

LeetCode刷题：301. Remove Invalid Parentheses

原题链接：

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()"

Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"

Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("

Output: [""]

删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。

说明: 输入可能包含了除 ( 和 ) 以外的字符。

算法设计

DFS算法设计

/*DFS*/	public List
   
     removeInvalidParentheses(String s) {        List
    
      ans = new ArrayList<>();        if (s == null)			return ans;		int removeLeft = 0, removeRight = 0;        for (char ch : s.toCharArray()) {            if (ch == '(')                removeLeft++;            if (ch == ')') {                if (removeLeft > 0)                    removeLeft--;                else                    removeRight++;            }        }                DFS(s, 0, removeLeft, removeRight, ans);                return ans;      //O(string length) + O()    }	    private void DFS(String s, int lastRemoveIndex, int removeLeft, int removeRight, List
     
       ans) {        if (removeLeft == 0 && removeRight == 0) { //O(N)            if (isValid(s))                ans.add(s);            return;        }                int idx = lastRemoveIndex;        if (removeRight > 0) {            while (idx < s.length()) {                if (s.charAt(idx) == ')') {                    DFS(s.substring(0, idx) + s.substring(idx + 1, s.length()), idx, removeLeft, removeRight - 1, ans);                    while (idx < s.length() && s.charAt(idx) == ')') idx++;                } else {                    idx++;                }            }            return;        }         if (removeLeft > 0) {            while (idx < s.length()) {                if (s.charAt(idx) == '(') {                    DFS(s.substring(0, idx) + s.substring(idx + 1, s.length()), idx, removeLeft - 1, removeRight, ans);                    while (idx < s.length() && s.charAt(idx) == '(') idx++;                } else {                    idx++;                }            }                    }            }    private boolean isValid(String s) {        if (s == null)            return false;        int cnt = 0;                for (char ch : s.toCharArray()) {            if (ch == '(') cnt++;            if (ch == ')') cnt--;            if (cnt < 0) return false;        }        return cnt == 0;    }

BFS算法设计

/*	 * BFS	 * */	public List
   
     removeInvalidParentheses(String s) {		List
    
      res = new ArrayList<>();		// sanity check		if (s == null)			return res;		Set
     
       visited = new HashSet<>();		Queue
      
        queue = new LinkedList<>();		// initialize		queue.add(s);		visited.add(s);		boolean found = false;		while (!queue.isEmpty()) {			s = queue.poll();			if (isValid(s)) {				// found an answer, add to the result				res.add(s);				found = true;			}			if (found)				continue;			// generate all possible states			for (int i = 0; i < s.length(); i++) {				// we only try to remove left or right paren				if (s.charAt(i) != '(' && s.charAt(i) != ')')					continue;				String t = s.substring(0, i) + s.substring(i + 1);				if (!visited.contains(t)) {					// for each state, if it's not visited, add it to the queue					queue.add(t);					visited.add(t);				}			}		}		return res;	}	// helper function checks if string s contains valid parantheses	boolean isValid(String s) {		int count = 0;		for (int i = 0; i < s.length(); i++) {			char c = s.charAt(i);			if (c == '(')				count++;			if (c == ')' && count-- == 0)				return false;		}		return count == 0;	}