KK's blog

LeetCode 207 Course Schedule

Posted on 2022-01-17 Edited on 2026-06-03 Disqus:

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints: 1 <= numCourses <= 105
0 <= prerequisites.length <= 5000 prerequisites[i].length == 2
0 <= ai, bi < numCourses All the pairs prerequisites[i] are unique.

题目大意：

课程有先修课要求，求是否可以完成所有课程

解题思路：

跟LeetCode 210 Course Schedule II几乎一样，此题求可否完成，那题求课程顺序。区别在于return那一句返回bool还是res

解题步骤：

N/A

注意事项：

Python代码：

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
	in_degree = [0] * numCourses
	graph = [[] for _ in range(numCourses)]
	for li in prerequisites:
		in_degree[li[0]] += 1
		graph[li[1]].append(li[0])
	queue = collections.deque([i for i in range(len(in_degree)) if in_degree[i] == 0])
	res = []
	while queue:
		node = queue.popleft()
		res.append(node)
		for neighbor in graph[node]:
			in_degree[neighbor] -= 1
			if in_degree[neighbor] == 0:
				queue.append(neighbor)
	return numCourses == len(res)

算法分析：

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

LeetCode 211 Design Add and Search Words Data Structure

Posted on 2022-01-17 Edited on 2026-06-03 Disqus:

LeetCode

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object. void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
[“WordDictionary”,”addWord”,”addWord”,”addWord”,”search”,”search”,”search”,”search”]
[[],[“bad”],[“dad”],[“mad”],[“pad”],[“bad”],[“.ad”],[“b..”]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord(“bad”);
wordDictionary.addWord(“dad”);
wordDictionary.addWord(“mad”);
wordDictionary.search(“pad”); // return False
wordDictionary.search(“bad”); // return True
wordDictionary.search(“.ad”); // return True
wordDictionary.search(“b..”); // return True

Constraints: 1 <= word.length <= 500
word in addWord consists lower-case English letters. word in search consist of '.' or lower-case English letters.
* At most 50000 calls will be made to addWord and search.

题目大意：

设计一个数据结构支持加单词和查找单词。查找单词支持dot查询，表示配对任意字符

解题思路：

第一时间想到Trie，但难点在如果支持dot。一般Trie实现只支持单一单词查询，但是此题需要搜索所有可能节点。所以要将search加入TrieNode参数且转成DFS

解题步骤：

N/A

注意事项：

search加入TrieNode参数且转成DFS
终止条件第二个用TrieNode为空而不是用is_end

Python代码：

class WordDictionary(TestCases):

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

    def addWord(self, word: str) -> None:
        it = self.head
        for i in range(len(word)):
            it = it.children[word[i]]
        it.is_end = True

    def search(self, word: str) -> bool:
        return self.search_one_node(word, self.head)

    def search_one_node(self, word, trie_node) -> bool:
        if not word and trie_node.is_end:
            return True
        if not word or not trie_node: # remember not trie_node
            return False
        if word[0] == '.':
            for child_node in trie_node.children.values():
                if self.search_one_node(word[1:], child_node):
                    return True
            return False
        if word[0] not in trie_node.children:
            return False
        return self.search_one_node(word[1:], trie_node.children[word[0]])

class TrieNode:

    def __init__(self):
        self.children = collections.defaultdict(TrieNode)  # {}
        self.is_end = False

算法分析：

search中不含dot时间复杂度为O(n), 含dot时间复杂度为O(26ⁿ)，空间复杂度O(1), n为搜索单词长度.

LeetCode 091 Decode Ways

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

LeetCode

A message containing letters from A-Z can be encoded into numbers using the following mapping:

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6) "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: s = “12”
Output: 2
Explanation: “12” could be decoded as “AB” (1 2) or “L” (12).

Example 2:

Input: s = “226”
Output: 3
Explanation: “226” could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).

Example 3:

Input: s = “06”
Output: 0
Explanation: “06” cannot be mapped to “F” because of the leading zero (“6” is different from “06”).

Constraints:

1 <= s.length <= 100 s contains only digits and may contain leading zero(s).

题目大意：

数字1-26可以解码成A-Z字母。给定一串数字，求解码方法数。

解题思路：

求种数是DP和DFS，这题有递归关系，所以考虑用DP。类似于Fibonacci数列和LeetCode 070 Climbing Stairs，但此题带限制条件

递归式：

1	dp[i] = dp[i-1] + dp[i-2] if 0 < s[i-1] <= 9, 10 <= s[i-2:i] <= 26

解题步骤：

利用DP五点注意事项

注意事项：

不合法的情况为空字符和含0. 这是求个数，根据DP知识点(数值到个数DP模板)，dp[0] = 1, 但这与题目空字符要求不同，所以特别处理。至于单个含0在循环中处理’0’ < s[i - 1] <= ‘9’
验证单位范围[1, 9], 双位范围[10, 26]才加入到结果中。由于dp长度只多了一位而递归式含两个前状态，所以要验证i >= 2

Python代码：

# dp[i] = dp[i-1] + dp[i-2] if 0 < s[i-1] <= 9, 10 <= s[i-2:i] <= 26
def numDecodings(self, s: str) -> int:
	if not s:
		return 0
	dp = [0] * (len(s) + 1)
	dp[0] = 1
	for i in range(1, len(dp)):
		if '0' < s[i - 1] <= '9':
			dp[i] = dp[i - 1]
		if i >= 2 and '10' <= s[i - 2: i] <= '26':
			dp[i] += dp[i - 2]
	return dp[-1]

算法分析：

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

O(1)空间算法II解题思路：

类似于Fibonacci数列和LeetCode 070 Climbing Stairs，由于涉及到两个前状态，所以用两个变量来节省空间

Python代码：

# dp[i] = dp[i-1] + dp[i-2] if 0 < s[i-1] <= 9, 10 <= s[i-2:i] <= 26
def numDecodings2(self, s: str) -> int:
	if not s:
		return 0
	first, second = 1, 1
	for i in range(1, len(s) + 1):
		res = 0
		if '0' < s[i - 1] <= '9':
			res = second
		if i >= 2 and '10' <= s[i - 2: i] <= '26':
			res += first
		first, second = second, res
	return res

算法分析：

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

LeetCode 093 Restore IP Addresses

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

LeetCode

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

Example 1:

Input: s = “25525511135”
Output: [“255.255.11.135”,”255.255.111.35”]

Example 2:

Input: s = “0000”
Output: [“0.0.0.0”]

Example 3:

Input: s = “101023”
Output: [“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]

Constraints: 0 <= s.length <= 20
* s consists of digits only.

题目大意：

给定一个数字字符串，求以分解成合法IP的所有解。IP每段范围是0-255且不能有前缀0，如06

解题思路：

求所有解，所以用DFS

解题步骤：

N/A

注意事项：

用DFS模板，属于结果分组型DFS，dfs函数有k。
两个限制条件，不能含leading zero和数字范围在255内

Python代码：

def restoreIpAddresses(self, s: str) -> List[str]:
	res = []
	self.dfs(s, 0, [], res, 4)
	return res

def dfs(self, s, st, path, res, k):
	if st == len(s) and k == 0:
		res.append('.'.join(path))
		return
	if st == len(s) or k == 0:
		return
	for i in range(st, min(st + 3, len(s))):
		segment = s[st:i + 1]
		if len(segment) > 1 and segment[0] == '0': # no leading 0
			continue
		if int(segment) > 255: # remember
			continue
		path.append(segment)
		self.dfs(s, i + 1, path, res, k - 1)
		path.pop()

算法分析：

时间复杂度为O(1)，空间复杂度O(1), 由于IP固定是4个部分，每个部分最多3位，所以乘法原理第一个dot的选择有三个位置，其他两个dot如此类推，3x3x3=27

LeetCode 100 Same Tree

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

LeetCode

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints:

The number of nodes in both trees is in the range [0, 100]. -104 <= Node.val <= 104

题目大意：

判断二叉树是否相等

解题思路：

类似于Leetcode 101 Symmetric Tree但稍简单, easy题

解题步骤：

N/A

注意事项：

Python代码：

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
	if not p and not q:
		return True
	if not p or not q:
		return False
	return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

算法分析：

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