Leetcode 2135: Count Words Obtained After Adding a Letter
Given two arrays of strings,
startWords and targetWords, determine how many strings in targetWords can be formed by appending a letter to any string in startWords and rearranging the letters.Problem
Approach
Steps
Complexity
Input: Two arrays of strings `startWords` and `targetWords`, each containing lowercase English letters.
Example: startWords = ["rat", "tap", "part"], targetWords = ["trap", "pat", "partz"]
Constraints:
• 1 <= startWords.length, targetWords.length <= 5 * 10^4
• 1 <= startWords[i].length, targetWords[j].length <= 26
• Each string consists of lowercase English letters.
Output: Return the number of strings in `targetWords` that can be formed by appending a letter to a string in `startWords` and rearranging the letters.
Example: Output = 2
Constraints:
• The result is a non-negative integer.
Goal: Identify the number of words in `targetWords` that can be formed from `startWords` using the conversion operation.
Steps:
• Convert each word in `startWords` and `targetWords` to bitmasks.
• For each word in `targetWords`, check if a matching word in `startWords` exists where only one additional letter is needed.
Goal: The input arrays and strings should adhere to the specified constraints for efficiency.
Steps:
• startWords and targetWords can each contain up to 50,000 strings.
• Each string has a maximum length of 26 characters.
Assumptions:
• The strings in both arrays consist of lowercase English letters only.
• No string in `startWords` or `targetWords` contains duplicate letters.
• Input: startWords = ["rat", "tap", "part"], targetWords = ["trap", "pat", "partz"]
• Explanation: From 'rat' we can form 'trap', from 'tap' we can form 'pat', but 'partz' cannot be formed.
Approach: Use bitmasking to represent the sets of characters in the words and check if appending one character to a word from `startWords` can form a word in `targetWords`.
Observations:
• The conversion operation involves appending one new character and rearranging the letters, which suggests using a bitmask representation.
• We can use a set to store the bitmasks of the start words and check for each target word if one of these masks can be transformed by adding a single bit.
Steps:
• Create bitmask representations of each word in `startWords`.
• For each word in `targetWords`, create its bitmask and check if adding one more bit results in a mask that exists in the `startWords` bitmask set.
Empty Inputs:
• Both `startWords` and `targetWords` are non-empty by problem constraints.
Large Inputs:
• Optimize the solution for large arrays with up to 50,000 strings.
Special Values:
• Consider words in `startWords` that are already identical to words in `targetWords` (no conversion needed).
Constraints:
• Ensure that no more than one letter is appended during the conversion operation.
int wordCount(vector<string>& start, vector<string>& end) {
set<int> bit;
for(auto it: start) {
int mask = 0;
for(char x: it)
mask |= 1 << (x - 'a');
bit.insert(mask);
}
int cnt = 0;
for(auto it: end) {
int mask = 0;
for(char x: it)
mask |= 1 << (x - 'a');
for(int i = 0; i < 26; i++) {
if(((mask >> i) & 1) == 0) continue;
int tmp = (mask ^ (1 << i));
if(bit.count(tmp)) {
cnt++;
break;
}
}
}
return cnt;
}
1 : Initialization
int wordCount(vector<string>& start, vector<string>& end) {
Declares the function `wordCount`, which takes two vectors of strings, `start` and `end`, and returns an integer count of words with similar masks.
2 : Variable Declaration
set<int> bit;
Declares a set `bit` to store unique masks representing characters in the strings from the `start` vector.
3 : Iteration
for(auto it: start) {
Iterates over each string in the `start` vector.
4 : Mask Calculation
int mask = 0;
Initializes a variable `mask` to 0, which will be used to store the bitwise representation of characters in the string.
5 : Character Iteration
for(char x: it)
Iterates over each character `x` in the current string `it`.
6 : Mask Update
mask |= 1 << (x - 'a');
Updates the mask by setting the bit corresponding to the character `x` in the range 'a' to 'z'.
7 : Mask Insertion
bit.insert(mask);
Inserts the computed `mask` into the `bit` set.
8 : Count Initialization
int cnt = 0;
Initializes a counter `cnt` to 0, which will store the number of valid words found in the `end` vector.
9 : End Vector Iteration
for(auto it: end) {
Iterates over each string in the `end` vector.
10 : Mask Calculation
int mask = 0;
Initializes a new variable `mask` for the current string from the `end` vector.
11 : Character Iteration
for(char x: it)
Iterates over each character `x` in the current string `it`.
12 : Mask Update
mask |= 1 << (x - 'a');
Updates the mask for the current string `it` in the `end` vector.
13 : Blank
Empty line for clarity.
14 : Bitwise Comparison
for(int i = 0; i < 26; i++) {
Iterates through each bit position (0 to 25) to check for possible matches.
15 : Skip if Bit Not Set
if(((mask >> i) & 1) == 0) continue;
Skips the current iteration if the bit at position `i` is not set in the current mask.
16 : Mask Update
int tmp = (mask ^ (1 << i));
Calculates a temporary mask by flipping the bit at position `i` in the current `mask`.
17 : Match Check
if(bit.count(tmp)) {
Checks if the modified `tmp` mask exists in the `bit` set.
18 : Count Increment
cnt++;
Increments the count `cnt` if a matching mask is found.
19 : Break Loop
break;
Breaks the inner loop as soon as a match is found.
20 : Return Count
return cnt;
Returns the count of words in `end` that have matching masks in `start`.
Best Case: O(n)
Average Case: O(n log n)
Worst Case: O(n * m)
Description: Where n is the number of words and m is the maximum word length. Time complexity is dominated by checking each target word against the set of bitmasks.
Best Case: O(n)
Worst Case: O(n)
Description: Space complexity is proportional to the number of words and the size of the bitmask set.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus