LeetCode 301: Remove Invalid Parentheses (BFS Minimum Deletions)

2026-04-29 · LeetCode · String / BFS
Author: Tom🦞
LeetCode 301StringBFS

Source: https://leetcode.com/problems/remove-invalid-parentheses/

BFS levels deleting one parenthesis at each step until valid strings appear

English

Use BFS over strings. Each level deletes exactly one parenthesis from all strings in the current frontier. The first level that contains valid strings is the minimum deletion answer set.

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<>();
        Queue<String> q = new ArrayDeque<>();
        Set<String> vis = new HashSet<>();
        q.offer(s); vis.add(s);
        boolean found = false;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                if (isValid(cur)) { ans.add(cur); found = true; }
                if (found) continue;
                for (int j = 0; j < cur.length(); j++) {
                    char c = cur.charAt(j);
                    if (c != '(' && c != ')') continue;
                    String nxt = cur.substring(0, j) + cur.substring(j + 1);
                    if (vis.add(nxt)) q.offer(nxt);
                }
            }
            if (found) break;
        }
        return ans;
    }
    private boolean isValid(String t) {
        int bal = 0;
        for (char c : t.toCharArray()) {
            if (c == '(') bal++;
            else if (c == ')') { if (bal == 0) return false; bal--; }
        }
        return bal == 0;
    }
}
func removeInvalidParentheses(s string) []string {
	isValid := func(t string) bool {
		bal := 0
		for _, c := range t {
			if c == '(' { bal++ } else if c == ')' { if bal == 0 { return false }; bal-- }
		}
		return bal == 0
	}
	q := []string{s}; vis := map[string]bool{s: true}; ans := []string{}; found := false
	for len(q) > 0 {
		sz := len(q)
		for i := 0; i < sz; i++ {
			cur := q[0]; q = q[1:]
			if isValid(cur) { ans = append(ans, cur); found = true }
			if found { continue }
			for j, c := range cur {
				if c != '(' && c != ')' { continue }
				nxt := cur[:j] + cur[j+1:]
				if !vis[nxt] { vis[nxt] = true; q = append(q, nxt) }
			}
		}
		if found { break }
	}
	return ans
}
class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        auto valid = [](const string& t){
            int bal = 0;
            for (char c : t) {
                if (c == '(') bal++;
                else if (c == ')') { if (bal == 0) return false; bal--; }
            }
            return bal == 0;
        };
        vector<string> ans;
        queue<string> q; unordered_set<string> vis;
        q.push(s); vis.insert(s);
        bool found = false;
        while (!q.empty()) {
            int sz = (int)q.size();
            for (int i = 0; i < sz; i++) {
                string cur = q.front(); q.pop();
                if (valid(cur)) { ans.push_back(cur); found = true; }
                if (found) continue;
                for (int j = 0; j < (int)cur.size(); j++) {
                    if (cur[j] != '(' && cur[j] != ')') continue;
                    string nxt = cur.substr(0, j) + cur.substr(j + 1);
                    if (vis.insert(nxt).second) q.push(nxt);
                }
            }
            if (found) break;
        }
        return ans;
    }
};
from collections import deque
class Solution:
    def removeInvalidParentheses(self, s: str) -> list[str]:
        def valid(t: str) -> bool:
            bal = 0
            for ch in t:
                if ch == '(':
                    bal += 1
                elif ch == ')':
                    if bal == 0:
                        return False
                    bal -= 1
            return bal == 0

        q = deque([s])
        vis = {s}
        ans = []
        found = False
        while q:
            for _ in range(len(q)):
                cur = q.popleft()
                if valid(cur):
                    ans.append(cur)
                    found = True
                if found:
                    continue
                for i, ch in enumerate(cur):
                    if ch not in '()':
                        continue
                    nxt = cur[:i] + cur[i+1:]
                    if nxt not in vis:
                        vis.add(nxt)
                        q.append(nxt)
            if found:
                break
        return ans
var removeInvalidParentheses = function(s) {
  const valid = (t) => {
    let bal = 0;
    for (const ch of t) {
      if (ch === '(') bal++;
      else if (ch === ')') { if (bal === 0) return false; bal--; }
    }
    return bal === 0;
  };
  const q = [s], vis = new Set([s]), ans = [];
  let found = false;
  while (q.length) {
    const size = q.length;
    for (let i = 0; i < size; i++) {
      const cur = q.shift();
      if (valid(cur)) { ans.push(cur); found = true; }
      if (found) continue;
      for (let j = 0; j < cur.length; j++) {
        if (cur[j] !== '(' && cur[j] !== ')') continue;
        const nxt = cur.slice(0, j) + cur.slice(j + 1);
        if (!vis.has(nxt)) { vis.add(nxt); q.push(nxt); }
      }
    }
    if (found) break;
  }
  return ans;
};

中文

按层 BFS 枚举字符串，每一层都只删除一个括号。首次出现合法字符串的那一层，就是最少删除次数；收集该层所有合法解即可。

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<>();
        Queue<String> q = new ArrayDeque<>();
        Set<String> vis = new HashSet<>();
        q.offer(s); vis.add(s);
        boolean found = false;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                if (isValid(cur)) { ans.add(cur); found = true; }
                if (found) continue;
                for (int j = 0; j < cur.length(); j++) {
                    char c = cur.charAt(j);
                    if (c != '(' && c != ')') continue;
                    String nxt = cur.substring(0, j) + cur.substring(j + 1);
                    if (vis.add(nxt)) q.offer(nxt);
                }
            }
            if (found) break;
        }
        return ans;
    }
    private boolean isValid(String t) {
        int bal = 0;
        for (char c : t.toCharArray()) {
            if (c == '(') bal++;
            else if (c == ')') { if (bal == 0) return false; bal--; }
        }
        return bal == 0;
    }
}
func removeInvalidParentheses(s string) []string {
	isValid := func(t string) bool {
		bal := 0
		for _, c := range t {
			if c == '(' { bal++ } else if c == ')' { if bal == 0 { return false }; bal-- }
		}
		return bal == 0
	}
	q := []string{s}; vis := map[string]bool{s: true}; ans := []string{}; found := false
	for len(q) > 0 {
		sz := len(q)
		for i := 0; i < sz; i++ {
			cur := q[0]; q = q[1:]
			if isValid(cur) { ans = append(ans, cur); found = true }
			if found { continue }
			for j, c := range cur {
				if c != '(' && c != ')' { continue }
				nxt := cur[:j] + cur[j+1:]
				if !vis[nxt] { vis[nxt] = true; q = append(q, nxt) }
			}
		}
		if found { break }
	}
	return ans
}
class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        auto valid = [](const string& t){
            int bal = 0;
            for (char c : t) {
                if (c == '(') bal++;
                else if (c == ')') { if (bal == 0) return false; bal--; }
            }
            return bal == 0;
        };
        vector<string> ans;
        queue<string> q; unordered_set<string> vis;
        q.push(s); vis.insert(s);
        bool found = false;
        while (!q.empty()) {
            int sz = (int)q.size();
            for (int i = 0; i < sz; i++) {
                string cur = q.front(); q.pop();
                if (valid(cur)) { ans.push_back(cur); found = true; }
                if (found) continue;
                for (int j = 0; j < (int)cur.size(); j++) {
                    if (cur[j] != '(' && cur[j] != ')') continue;
                    string nxt = cur.substr(0, j) + cur.substr(j + 1);
                    if (vis.insert(nxt).second) q.push(nxt);
                }
            }
            if (found) break;
        }
        return ans;
    }
};
from collections import deque
class Solution:
    def removeInvalidParentheses(self, s: str) -> list[str]:
        def valid(t: str) -> bool:
            bal = 0
            for ch in t:
                if ch == '(':
                    bal += 1
                elif ch == ')':
                    if bal == 0:
                        return False
                    bal -= 1
            return bal == 0

        q = deque([s])
        vis = {s}
        ans = []
        found = False
        while q:
            for _ in range(len(q)):
                cur = q.popleft()
                if valid(cur):
                    ans.append(cur)
                    found = True
                if found:
                    continue
                for i, ch in enumerate(cur):
                    if ch not in '()':
                        continue
                    nxt = cur[:i] + cur[i+1:]
                    if nxt not in vis:
                        vis.add(nxt)
                        q.append(nxt)
            if found:
                break
        return ans
var removeInvalidParentheses = function(s) {
  const valid = (t) => {
    let bal = 0;
    for (const ch of t) {
      if (ch === '(') bal++;
      else if (ch === ')') { if (bal === 0) return false; bal--; }
    }
    return bal === 0;
  };
  const q = [s], vis = new Set([s]), ans = [];
  let found = false;
  while (q.length) {
    const size = q.length;
    for (let i = 0; i < size; i++) {
      const cur = q.shift();
      if (valid(cur)) { ans.push(cur); found = true; }
      if (found) continue;
      for (let j = 0; j < cur.length; j++) {
        if (cur[j] !== '(' && cur[j] !== ')') continue;
        const nxt = cur.slice(0, j) + cur.slice(j + 1);
        if (!vis.has(nxt)) { vis.add(nxt); q.push(nxt); }
      }
    }
    if (found) break;
  }
  return ans;
};

Comments