KK's blog

LeetCode 1249 Minimum Remove to Make Valid Parentheses

Posted on 2022-03-16 Edited on 2026-06-03 Disqus:

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Example 1:

Input: s = “lee(t(c)o)de)”
Output: “lee(t(c)o)de”
Explanation: “lee(t(co)de)” , “lee(t(c)ode)” would also be accepted.

Example 2:

Input: s = “a)b(c)d”
Output: “ab(c)d”

Example 3:

Input: s = “))((“
Output: “”
Explanation: An empty string is also valid.

Example 4:

Input: s = “(a(b(c)d)”
Output: “a(b(c)d)”

Constraints: 1 <= s.length <= 10<sup>5</sup>
* s[i] is either'(' , ')', or lowercase English letter.

题目大意：

去掉最小不合法括号数剩下的字符串。

Stack算法思路：

括号题优先考虑用Stack。此题将下标存于stack中，stack留下的是不合法括号下标，也就是需要删除的

LeetCode 1249 Minimum Remove to Make Valid Parentheses 求一个最优解 Medium, Stack
LeetCode 921 Minimum Add to Make Parentheses Valid 求一个最优解 Medium, Stack
LeetCode 301 Remove Invalid Parentheses 求所有最优解 Hard，此题答案包含上题, BFS

注意事项：

当括号配对时才出栈 Line 6

Python代码：

def minRemoveToMakeValid(self, s: str) -> str:
	stack, res = [], ''
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
		elif stack and s[stack[-1]] == '(' and s[i] == ')':  # remember
			stack.pop()
		elif s[i] == ')':
			stack.append(i)
	for i in range(len(s)):
		if i in set(stack):
			continue
		res += s[i]
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

LeetCode 301 Remove Invalid Parentheses

Posted on 2022-03-16 Edited on 2026-06-03 Disqus:

LeetCode

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return all the possible results. You may return the answer in any order.

Example 1:

Input: s = “()())()”
Output: [“(())()”,”()()()”]

Example 2:

Input: s = “(a)())()”
Output: [“(a())()”,”(a)()()”]

Example 3:

Input: s = “)(“
Output: [“”]

Constraints:

1 <= s.length <= 25 s consists of lowercase English letters and parentheses '(' and ')'.
* There will be at most 20 parentheses in s.

题目大意：

求最小去掉不合法括号数之后的所有结果

算法思路：

最值问题考虑用DP和BFS，DP难以拆分子问题。所以考虑用BFS + 括号是否合法

LeetCode 1249 Minimum Remove to Make Valid Parentheses 求一个最优解 Medium, Stack
LeetCode 921 Minimum Add to Make Parentheses Valid 求一个最优解 Medium, Stack
LeetCode 301 Remove Invalid Parentheses 求所有最优解 Hard，此题答案包含上题, BFS

注意事项：

由于()())() -> (())()，所以去掉的括号不一定都不合法，所以BFS要尝试删除每一个括号。若节点合法，加入结果且记录最小删除数，因为要求同一距离下的所有结果，所以用这个最小数来剪枝。
输入含小写字母，所以无论是判断括号是否合法还是生成儿子节点都要跳过
模板中含if neighbor in visited，不能忘记写

Python代码：

def removeInvalidParentheses(self, s: str) -> List[str]:
	queue = collections.deque([s])
	visited = set([s])
	res, min_dis = [], float('inf')
	distance = collections.defaultdict(int)
	while queue:
		node = queue.popleft()
		if self.is_valid(node):
			res.append(node)
			min_dis = min(min_dis, distance[node])
			continue
		if distance[node] > min_dis:
			continue
		for i in range(len(node)):
			if node[i] not in ['(', ')']:  # remember
				continue
			child = node[:i] + node[i + 1:]
			if child in visited: # remember
				continue
			queue.append(child)
			visited.add(child)
			distance[child] = distance[node] + 1
	return res

def is_valid(self, s): # remember not to use get_invalid_index ()())() -> (())()
	stack = []
	for i, char in enumerate(s):
		if char not in ['(', ')']: # remember
			continue
		if char == ')' and stack and s[stack[-1]] == '(':
			stack.pop()
		else:
			stack.append(i)
	return False if stack else True

算法分析：

时间复杂度为O(2ⁿ)，空间复杂度O(n)

LeetCode 921 Minimum Add to Make Parentheses Valid

Posted on 2022-03-16 Edited on 2026-06-03 Disqus:

LeetCode

A parentheses string is valid if and only if:

It is the empty string, It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string. For example, if s = "()))", you can insert an opening parenthesis to be "(**(**)))" or a closing parenthesis to be "())**)**)".

Return the minimum number of moves required to make s valid.

Example 1:

Input: s = “())”
Output: 1

Example 2:

Input: s = “(((“
Output: 3

Constraints:

1 <= s.length <= 1000 s[i] is either '(' or ')'.

题目大意：

最小加括号数使得配对

Stack解题思路(推荐)：

跟Leetcode 1249一样。括号题优先考虑用Stack。此题将下标存于stack中，stack留下的是不合法括号下标，也就是需要删除的

LeetCode 1249 Minimum Remove to Make Valid Parentheses 求一个最优解 Medium, Stack
LeetCode 921 Minimum Add to Make Parentheses Valid 求一个最优解 Medium, Stack
LeetCode 301 Remove Invalid Parentheses 求所有最优解 Hard，此题答案包含上题, BFS

解题步骤：

注意事项：

Python代码：

def minAddToMakeValid(self, s: str) -> int:
	stack, res = [], ''
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
		elif stack and s[stack[-1]] == '(' and s[i] == ')':  # remember
			stack.pop()
		elif s[i] == ')':
			stack.append(i)
	return len(stack)

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

统计算法II解题思路：

类似于Leetcode 032 Longest Valid Parentheses的统计算法。用这两种情况来写即可： ()), )(. 若左括号数left出现负数，根据第一个规律，重设left，计入res

Python代码：

def minAddToMakeValid2(self, s: str) -> int:
	left, res = 0, 0
	for char in s:
		if char == '(':
			left += 1
		else:
			left -= 1
			if left < 0:
				res += 1
				left = 0
	return res + abs(left)

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

LeetCode 938 Range Sum of BST

Posted on 2022-03-16 Edited on 2026-06-03 Disqus:

LeetCode

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.

Constraints:

The number of nodes in the tree is in the range `[1, 2 10⁴]

.
*

1 <= Node.val <= 10⁵*1 <= low <= high <= 10⁵* AllNode.val` are unique.

题目大意：

给定[low, high]和BST，求满足条件的BST的节点和

解题思路：

Easy题，DFS，条件比较容易错

解题步骤：

N/A

注意事项：

两个条件，若root.val在范围内，加入和。若low小于root.val(这里不取等号，因为所有节点是唯一，不存在相等节点)，
表示范围适用于左节点，同理右节点。

Python代码：

def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
	if not root:
		return 0
	res = 0
	if low <= root.val <= high:
		res += root.val
	if low < root.val:
		res += self.rangeSumBST(root.left, low, high)
	if root.val < high:
		res += self.rangeSumBST(root.right, low, high)
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

LeetCode 588 Design In-Memory File System

Posted on 2022-03-15 Edited on 2026-06-03 Disqus:

LeetCode

Design a data structure that simulates an in-memory file system.

Implement the FileSystem class:

FileSystem() Initializes the object of the system. List<String> ls(String path)
If path is a file path, returns a list that only contains this file’s name. If path is a directory path, returns the list of file and directory names in this directory.The answer should in lexicographic order.
void mkdir(String path) Makes a new directory according to the given path. The given directory path does not exist. If the middle directories in the path do not exist, you should create them as well. void addContentToFile(String filePath, String content)
If filePath does not exist, creates that file containing given content. If filePath already exists, appends the given content to original content.
String readContentFromFile(String filePath) Returns the content in the file at filePath.

Example 1:

Input
[“FileSystem”, “ls”, “mkdir”, “addContentToFile”, “ls”, “readContentFromFile”]
[[], [“/“], [“/a/b/c”], [“/a/b/c/d”, “hello”], [“/“], [“/a/b/c/d”]]
Output
[null, [], null, null, [“a”], “hello”]

Explanation
FileSystem fileSystem = new FileSystem();
fileSystem.ls(“/“); // return []
fileSystem.mkdir(“/a/b/c”);
fileSystem.addContentToFile(“/a/b/c/d”, “hello”);
fileSystem.ls(“/“); // return [“a”]
fileSystem.readContentFromFile(“/a/b/c/d”); // return “hello”

Constraints: 1 <= path.length, filePath.length <= 100
path and filePath are absolute paths which begin with '/' and do not end with '/' except that the path is just "/". You can assume that all directory names and file names only contain lowercase letters, and the same names will not exist in the same directory.
You can assume that all operations will be passed valid parameters, and users will not attempt to retrieve file content or list a directory or file that does not exist. 1 <= content.length <= 50
* At most 300 calls will be made to ls, mkdir, addContentToFile, and readContentFromFile.

题目大意：

设计文件系统

解题思路：

如数据库系统的B+树一样，用Trie

解题步骤：

N/A

注意事项：

TrieNode含children和files，都是dict，只能是目录节点。因为不知道最后一个路劲部分是文件还是目录，所以ls里面需要遍历直到倒数第二个节点，再判断是哪种情况。另一个种设计是采取is_file, content，既可以是目录节点也可以是文件节点，本文采取前者
ls:题目要求目录可以含目录和文件。两种情况：若是文件，返回[文件]含在一个list中；若是目录，返回它下面的目录+文件
ls:返回结果要排序
ls:输入path可以是/或/a/b，所以/要特殊化处理，只能是目录，所以只有一种情况：目录和文件
_dir而不是dir, path而不是filepath，注意变量要用同一个

Python代码：

class Solution(TestCases):

    def __init__(self):
        self.root = TrieNode()

    def ls(self, path: str) -> List[str]:  # req remember /a not /a/
        if path == '/':
            return sorted(list(self.root.children.keys()) + list(self.root.files.keys())) # remember

        dirs = path[1:].split('/')
        it = self._ls(dirs[:-1])
        if dirs[-1] in it.files:
            return [dirs[-1]]
        else: # return files if no dir, no mixed types in same dir
            return sorted(list(it.children[dirs[-1]].children.keys()) + list(it.children[dirs[-1]].files.keys()))

    def mkdir(self, path: str) -> None:
        path = path[1:]
        dirs = path.split('/') # [a,b,c]
        self._mkdir(dirs)

    def addContentToFile(self, filePath: str, content: str) -> None:
        filePath = filePath[1:]
        dirs = filePath.split('/') # [a,b,c]
        it = self._mkdir(dirs[:-1])
        filename = dirs[-1]
        if filename not in it.files:
            it.files[filename] = ''
        it.files[filename] += content

    def readContentFromFile(self, filePath: str) -> str:
        filePath = filePath[1:]
        dirs = filePath.split('/')  # [a,b,c]
        it = self._ls(dirs[:-1])
        return it.files[dirs[-1]]

    def _ls(self, dirs):
        it = self.root
        for _dir in dirs:
            it = it.children[_dir]
        return it

    def _mkdir(self, dirs):
        it = self.root
        for _dir in dirs:
            it = it.children[_dir]
        return it

class TrieNode:

    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.files = collections.defaultdict(str) # use dict coz filename can't be duplicate and faster for lookup

算法分析：

时间复杂度为O(n)，空间复杂度O(n), n为路径长度