KK's blog

LeetCode 809 Expressive Words

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

Sometimes people repeat letters to represent extra feeling. For example:

"hello" -> "heeellooo" "hi" -> "hiiii"

In these strings like "heeellooo", we have groups of adjacent letters that are all the same: "h", "eee", "ll", "ooo".

You are given a string s and an array of query strings words. A query word is stretchy if it can be made to be equal to s by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is three or more.

For example, starting with "hello", we could do an extension on the group "o" to get "hellooo", but we cannot get "helloo" since the group "oo" has a size less than three. Also, we could do another extension like "ll" -> "lllll" to get "helllllooo". If s = "helllllooo", then the query word "hello" would be stretchy because of these two extension operations: query = "hello" -> "hellooo" -> "helllllooo" = s.

Return the number of query strings that are stretchy.

Example 1:

Input: s = “heeellooo”, words = [“hello”, “hi”, “helo”]
Output: 1
Explanation:
We can extend “e” and “o” in the word “hello” to get “heeellooo”.
We can’t extend “helo” to get “heeellooo” because the group “ll” is not size 3 or more.

Example 2:

Input: s = “zzzzzyyyyy”, words = [“zzyy”,”zy”,”zyy”]
Output: 3

Constraints: 1 <= s.length, words.length <= 100
1 <= words[i].length <= 100 s and words[i] consist of lowercase letters.

题目大意：

Cisco常考题
定义了一种富于表现力的单词，就是说某个字母可以重复三次或以上，叫stretchy
找给定的单词列表中的单词可以成为stretchy单词的个数

解题思路：

统计每个字符的个数，然后比较对应每个字符个数

解题步骤：

N/A

注意事项：

Line 13的条件，若个数不等，word的字符个数大于stretchy的字符个数(word不能删除字符)，或者stretchy的个数小于3，就不满足

Python代码：

def expressiveWords(self, s: str, words: List[str]) -> int:
	res = 0
	s_count = self.get_consecutive_count(s)
	for word in words:
		char_count = self.get_consecutive_count(word)
		if len(char_count) != len(s_count):
			continue
		for i in range(len(s_count)):
			char_s, count_s = s_count[i]
			char_w, count_w = char_count[i]
			if char_w != char_s:
				break
			if count_s != count_w and (count_w > count_s or count_s < 3): # remember
				break
			if i == len(s_count) - 1:
				res += 1
	return res

def get_consecutive_count(self, s):
	s += ' '
	s_count, count = [], 1
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			s_count.append((s[i - 1], count))
			count = 0
		count += 1
	return s_count

算法分析：

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

LeetCode 259 3Sum Smaller

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

LeetCode

Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Example 1:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

Example 2:

Input: nums = [], target = 0
Output: 0

Example 3:

Input: nums = [0], target = 0
Output: 0

Constraints:

n == nums.length 0 <= n <= 3500
-100 <= nums[i] <= 100 -100 <= target <= 100

题目大意：

找三数和小于target的组合个数

解题思路：

类似于三数和等于target，但当小于target时，直接求个数，类似于LeetCode 315 Count of Smaller Numbers After Self。

解题步骤：

N/A

注意事项：

res不是+1而是right - left

Python代码：

def threeSumSmaller(self, nums: List[int], target: int) -> int:
	if len(nums) < 3:
		return 0
	nums.sort()
	res = 0
	for i in range(len(nums) - 2):
		left, right = i + 1, len(nums) - 1
		while left < right:
			if nums[i] + nums[left] + nums[right] < target:
				res += right - left # remember
				left += 1
			else:
				right -= 1
	return res

算法分析：

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

LeetCode 628 Maximum Product of Three Numbers

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

LeetCode

Given an integer array nums, find three numbers whose product is maximum and return the maximum product.

Example 1:

Input: nums = [1,2,3]
Output: 6

Example 2:

Input: nums = [1,2,3,4]
Output: 24

Example 3:

Input: nums = [-1,-2,-3]
Output: -6

Constraints:

3 <= nums.length <= 104 -1000 <= nums[i] <= 1000

题目大意：

求数组任意三个数的最大乘积

排序法解题思路：

数学题，正负数分开，最大只可以是排序后最大的三个数(全正，全负)或最大整数乘以最小两个负数(正负均有)

解题步骤：

N/A

注意事项：

Python代码：

1
2
3

def maximumProduct(self, nums: List[int]) -> int:
	nums.sort()
	return max(nums[-1] * nums[-2] * nums[-3], nums[-1] * nums[0] * nums[1])

算法分析：

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

Heap算法II解题思路：

由上述思路进一步优化，不需要全部排序，只需要知道最大的3个数和最小的两个数即可

Python代码：

def maximumProduct2(self, nums: List[int]) -> int:
	largest = heapq.nlargest(3, nums)
	smallest = heapq.nsmallest(2, nums)
	return max(largest[0] * largest[1] * largest[2], largest[0] * smallest[0] * smallest[1])

算法分析：

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

LeetCode 1048 Longest String Chain

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

LeetCode 1048 Longest String Chain

You are given an array of words where each word consists of lowercase English letters.

wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.

For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".

A word chainis a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

Example 1:

Input: words = [“a”,”b”,”ba”,”bca”,”bda”,”bdca”]
Output: 4
Explanation: One of the longest word chains is [“a”,”ba”,”bda”,”bdca”].

Example 2:

Input: words = [“xbc”,”pcxbcf”,”xb”,”cxbc”,”pcxbc”]
Output: 5
Explanation: All the words can be put in a word chain [“xb”, “xbc“, “cxbc”, “pcxbc”, “pcxbcf“].

Example 3:

Input: words = [“abcd”,”dbqca”]
Output: 1
Explanation: The trivial word chain [“abcd”] is one of the longest word chains.
[“abcd”,”dbqca”] is not a valid word chain because the ordering of the letters is changed.

Constraints: 1 <= words.length <= 1000
1 <= words[i].length <= 16 words[i] only consists of lowercase English letters.

Problem Overview

Get longgest one-character transformation in the given list

Thinking Process

This problem is similar to Word Break (reversed to get neighbors) but it is a multi-source longest path problem.

Steps

Loop through each word
BFS from each word and get the max distance
Get the max of distance

Notes

max_dis = 1 by default in BFS
To improve the complexity, make the distance map global so that the distance of each node will be calculated once.
To do that, sort the list from longest to shortest and make sure the it is greedy to get the max distance

Python代码：

def longestStrChain(self, words: List[str]) -> int:
	word_dict, distance = set(words), {}
	max_dis = 0
	words.sort(key=len, reverse=True)  # remember
	for word in words:
		dis = self.bfs(word, word_dict, distance)
		max_dis = max(max_dis, dis)
	return max_dis

def bfs(self, word, word_dict, distance):
	queue = deque([word])
	visited = {word}
	if word in distance:  # remember
		return distance[word]
	distance[word] = 1
	max_dis = 1
	while queue:
		node = queue.popleft()
		for neighbor in self.get_neighbors(node, word_dict):
			if neighbor in visited:
				continue
			queue.append(neighbor)
			visited.add(neighbor)
			distance[neighbor] = distance[node] + 1
			max_dis = max(max_dis, distance[neighbor])
	return max_dis

def get_neighbors(self, word, word_dict):
	res = []
	for i in range(len(word)):
		new_word = word[:i] + word[i + 1:]
		if new_word in word_dict:
			res.append(new_word)
	return res

Analysis

Though there is a loop and bfs like n^2, actually it is a traversal in a graph. n * L (n is # of nodes, L is max of path
single-source) is the num of edges. Another L is to get neighbors.
Time complexityO(nlogn + n*L²), Space complexityO(n).

LeetCode 384 Shuffle an Array

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

LeetCode

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

Solution(int[] nums) Initializes the object with the integer array nums. int[] reset() Resets the array to its original configuration and returns it.
int[] shuffle() Returns a random shuffling of the array.

Example 1:

Input
[“Solution”, “shuffle”, “reset”, “shuffle”]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // Shuffle the array [1,2,3] and return its result.
// Any permutation of [1,2,3] must be equally likely to be returned.
// Example: return [3, 1, 2]
solution.reset(); // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle(); // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]

Constraints: 1 <= nums.length <= 200
-106 <= nums[i] <= 106 All the elements of nums are unique.
At most `5 10⁴calls **in total** will be made toresetandshuffle`.

题目大意：

随机重排数组

解题思路：

水塘抽样法

先看算法，再理解，第i个元素会被交换的概率：
某一个元素保留概率为(n - i) / (n - i + 1)
某一个元素交换概率为1 / (n - i)
所以从左到右遍历到第i个元素时，它被交换到后面的概率为所有前面都保留乘以第i轮循环时被交换：

1	(n - 1) / n * (n - 2) / (n - 1) ... (n - i) / (n - i + 1) * 1 / (n - i)

前面都约了，最后等于1 / n

解题步骤：

N/A

注意事项：

死记算法，跟后面的元素互换
复制原数组以防被改

Python代码：

def __init__(self, nums: List[int]):
	self.original = list(nums)
	self.nums = nums

def reset(self) -> List[int]:
	return list(self.original)

def shuffle(self) -> List[int]:
	for i in range(len(self.nums)):
		swap_idx = random.randrange(i, len(self.nums))
		self.nums[i], self.nums[swap_idx] = self.nums[swap_idx], self.nums[i]
	return self.nums

算法分析：

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