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 <= 100s and words[i] consist of lowercase letters.
defexpressiveWords(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) iflen(char_count) != len(s_count): continue for i inrange(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
defget_consecutive_count(self, s): s += ' ' s_count, count = [], 1 for i inrange(1, len(s)): if s[i] != s[i - 1]: s_count.append((s[i - 1], count)) count = 0 count += 1 return s_count
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.length0 <= 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代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14
defthreeSumSmaller(self, nums: List[int], target: int) -> int: iflen(nums) < 3: return0 nums.sort() res = 0 for i inrange(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
You are given an array of words where each word consists of lowercase English letters.
word<sub>A</sub> is a predecessor of word<sub>B</sub> if and only if we can insert exactly one letter anywhere in word<sub>A</sub>without changing the order of the other characters to make it equal to word<sub>B</sub>.
For example, "abc" is a predecessor of "ab<u>a</u>c", while "cba" is not a predecessor of "bcad".
A word chainis a sequence of words [word<sub>1</sub>, word<sub>2</sub>, ..., word<sub>k</sub>] with k >= 1, where word<sub>1</sub> is a predecessor of word<sub>2</sub>, word<sub>2</sub> is a predecessor of word<sub>3</sub>, 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 ofwords.
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 <= 16words[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
defbfs(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 inself.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
defget_neighbors(self, word, word_dict): res = [] for i inrange(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*L2), Space complexityO(n).
