KK's blog

LeetCode 301 Remove Invalid Parentheses

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

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为路径长度

LeetCode 706 Design HashMap

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

LeetCode

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map. void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key. void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Example 1:

Input
[“MyHashMap”, “put”, “put”, “get”, “get”, “put”, “get”, “remove”, “get”]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now [[1,1]]

Constraints:

0 <= key, value <= 10<sup>6</sup> At most 10<sup>4</sup> calls will be made to put, get, and remove.

题目大意：

设计HashMap

LL解题思路(推荐)：

大学学到的方法，用Array实现，将key mod prime num找到index插入。难点在于冲突处理，这里用chaining方法，也就是LL

解题步骤：

N/A

注意事项：

迭代LL时候，每种方法put, get, remove都不同。put只能迭代到最后一个不能到None，因为要从尾部加入。
get正常一个个迭代。remove要从parent也就是it.next迭代因为要删除节点。

Python代码：

class MyHashMap(TestCases):

    def __init__(self):
        self.key_space = 997
        self.buckets = [ListNode(-1, -1) for _ in range(self.key_space)]

    def put(self, key: int, value: int) -> None:
        index = key % self.key_space
        it = self.buckets[index]
        while it:
            if it.key == key:
                it.val = value
                return
            if not it.next:
                break
            it = it.next
        it.next = ListNode(key, value)

    def get(self, key: int) -> int:
        index = key % self.key_space
        it = self.buckets[index]
        while it:
            if it.key == key:
                return it.val
            it = it.next
        return -1

    def remove(self, key: int) -> None:
        index = key % self.key_space
        it = self.buckets[index]
        while it.next:
            if it.next.key == key:
                tmp = it.next
                it.next, tmp.next = it.next.next, None
                return
            it = it.next


class ListNode:

    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None

算法分析：

时间复杂度为O(k)，空间复杂度O(n), k为冲突数

数组算法II解题思路：

较容易实现，remove复杂度稍差，但是最差情况也是同上

Python代码：

class MyHashMap(TestCases):

    def __init__(self):
        self.key_space = 997
        self.buckets = [[] for _ in range(self.key_space)]

    def put(self, key: int, value: int) -> None:
        index = key % self.key_space
        for i, [_key, _val] in enumerate(self.buckets[index]):
            if _key == key:
                self.buckets[index][i] = [key, value]
                return
        self.buckets[index].append([key, value])

    def get(self, key: int) -> int:
        index = key % self.key_space
        for _key, _val in self.buckets[index]:
            if _key == key:
                return _val
        return -1

    def remove(self, key: int) -> None:
        index = key % self.key_space
        for i, [_key, _val] in enumerate(self.buckets[index]):
            if _key == key:
                self.buckets[index].pop(i)
                return

算法分析：

时间复杂度为O(k)，空间复杂度O(n), k为冲突数