KK's blog

LeetCode 076 Minimum Window Substring

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

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring__, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = “ADOBECODEBANC”, t = “ABC”
Output: “BANC”
Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.

Example 2:

Input: s = “a”, t = “a”
Output: “a”
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = “a”, t = “aa”
Output: “”
Explanation: Both ‘a’s from t must be included in the window.
Since the largest window of s only has one ‘a’, return empty string.

Constraints:

m == s.length n == t.length
1 <= m, n <= 105 s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

题目大意：

最短摘要：给定s和t两个字符串，求在s中包含所有t的字符的最短子串。这个结果可以包含不在t的字符，某个字符数量也可以多于t中的字符但不能少于。

解题思路：

提到window substring就用滑动窗口或者同向双指针。

解题步骤：

N/A

注意事项：

用同向双指针模板。用map来统计t的字符频率，用unique_count统计满足条件唯一字符个数。while的条件为unique_count达到了map的大小。
while里面的统计与while外面的统计本质一样，但相反。若s中某字符多于s中的，map为负值，left指针右移时，负值会变回正值。

Python代码：

def minWindow(self, s: str, t: str) -> str:
	t_char_to_count = collections.Counter(t)
	left, unique_count, min_len, res = 0, 0, float('inf'), ''
	for i in range(len(s)):
		if s[i] in t_char_to_count:
			t_char_to_count[s[i]] -= 1
			if t_char_to_count[s[i]] == 0:
				unique_count += 1
		while unique_count == len(t_char_to_count):
			if i - left + 1 < min_len:
				min_len = i - left + 1
				res = s[left:i + 1]
			if s[left] in t_char_to_count:
				t_char_to_count[s[left]] += 1
				if t_char_to_count[s[left]] == 1:
					unique_count -= 1
			left += 1
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(m), n和m分别为s和t的长度

LeetCode 408 Valid Word Abbreviation

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

LeetCode

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros.

For example, a string such as "substitution" could be abbreviated as (but not limited to):

"s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion")
"12" ("substitution") "su3i1u2on" ("su bst i t u ti on")
"substitution" (no substrings replaced)

The following are not valid abbreviations: "s55n" ("s ubsti tutio n", the replaced substrings are adjacent)
"s010n" (has leading zeros) "s0ubstitution" (replaces an empty substring)

Given a string word and an abbreviation abbr, return whether the string matches the given abbreviation.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: word = “internationalization”, abbr = “i12iz4n”
Output: true
Explanation: The word “internationalization” can be abbreviated as “i12iz4n” (“i nternational iz atio n”).

Example 2:

Input: word = “apple”, abbr = “a2e”
Output: false
Explanation: The word “apple” cannot be abbreviated as “a2e”.

Constraints:

1 <= word.length <= 20 word consists of only lowercase English letters.
1 <= abbr.length <= 10 abbr consists of lowercase English letters and digits.
* All the integers in abbr will fit in a 32-bit integer.

题目大意：

验证第二字符串是否第一字符串的一个种简写形式，用数字代替字符串部分长度

解题思路：

Easy题

解题步骤：

注意事项：

用内外while循环如quicksort的不推荐的算法，内循环的条件一定要复制外循环的条件j < len(abbr)
题目条件不能含前缀0，包括0本身，若数字第一位为0，就返回False

Python代码：

def validWordAbbreviation(self, word: str, abbr: str) -> bool:
	i, j, num = 0, 0, 0
	while i < len(word) and j < len(abbr):
		num_str = ''
		while j < len(abbr) and abbr[j].isdigit(): # remember j < len(abbr)
			num_str += abbr[j]
			j += 1
		if num_str:
			if num_str[0] == '0': # remember
				return False
			i += int(num_str)
		elif word[i] != abbr[j]:
			return False
		else:
			i += 1
			j += 1
	return False if i != len(word) or j != len(abbr) else True

算法分析：

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

LeetCode 426 Convert Binary Search Tree to Sorted Doubly Linked List

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

LeetCode

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

Example 1:

Input: root = [4,2,5,1,3]


Output: [1,2,3,4,5]

Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

Example 2:

Input: root = [2,1,3]
Output: [1,2,3]

Constraints:

The number of nodes in the tree is in the range [0, 2000]. -1000 <= Node.val <= 1000
All the values of the tree are *unique.

题目大意：

将二叉树变成双向链表，left为父节点，right为儿子节点

解题思路：

类似于LeetCode 114 Flatten Binary Tree to Linked List，先假设左右儿子，已经是双向LL，下面就是将root这个节点插入到两个LL之间其将它们首尾相连

解题步骤：

N/A

注意事项：

要将左右儿子节点的LL，首尾相连。首尾节点获得要在if语句前，因为右儿子的left会连到root，就找不到它的尾部。首尾相连要发生在最后。

Python代码：

def treeToDoublyList(self, root: 'Node') -> 'Node':
	if not root:
		return None
	if not root.left and not root.right:
		root.left, root.right = root, root
		return root
	left_head = self.treeToDoublyList(root.left)
	right_head = self.treeToDoublyList(root.right)
	# remember this part and order, can't be placed after ifs
	new_head = left_head if left_head else root
	new_tail = right_head.left if right_head else root
	if left_head:
		left_head.left.right, root.left = root, left_head.left
	if right_head:
		root.right, right_head.left = right_head, root
	new_head.left, new_tail.right = new_tail, new_head
	return new_head

算法分析：

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

LeetCode 791 Custom Sort String

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

LeetCode

You are given two strings order and s. All the words of order are unique and were sorted in some custom order previously.

Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.

Return any permutation of s that satisfies this property.

Example 1:

Input: order = “cba”, s = “abcd”
Output: “cbad”
Explanation:
“a”, “b”, “c” appear in order, so the order of “a”, “b”, “c” should be “c”, “b”, and “a”.
Since “d” does not appear in order, it can be at any position in the returned string. “dcba”, “cdba”, “cbda” are also valid outputs.

Example 2:

Input: order = “cbafg”, s = “abcd”
Output: “cbad”

Constraints:

1 <= order.length <= 26 1 <= s.length <= 200
order and s consist of lowercase English letters. All the characters of order are unique.

题目大意：

给一个字符串，求这个字符串的一个排列，使得字母顺序按照另一个给定字符串order的顺序。

解题思路：

由限制条件知道，order字母是唯一的，order字母可以重复。所以只要统计s频率，然后按照字母顺序开始重写

解题步骤：

N/A

注意事项：

Python代码：

def customSortString(self, order: str, s: str) -> str:
	char_to_count = collections.Counter(s)
	res = ''
	for c in order:
		if c in char_to_count:
			res += c * char_to_count[c]
			char_to_count.pop(c)
	for c, count in char_to_count.items():
		res += c * count
	return res

算法分析：

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

LeetCode 1249 Minimum Remove to Make Valid Parentheses

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

LeetCode

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 <= 105
* 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)