πΉ Problem: 2135 Count Words Obtained After Adding a Letter
Difficulty: #Medium
Tags: #BitMsk, #Hashing, #Set, #Strings
π Problem Summary
You're given two lists of unique words: startWords and targetWords.
You can transform a word from startWords into a targetWord by:
- Adding exactly one letter anywhere in the word.
- Then rearranging the resulting word.
You need to return the number of targetWords that can be obtained this way from any startWord.
π§ My Thought Process
Brute Force Idea:
Try all possible pairs betweenstartWordsandtargetWords. For each, add one character tostartWord, sort, and check if it matches atargetWord.
β Too slow. Time complexity is O(N * M * log L).-
Optimized Strategy:
Use bitmasking to represent character presence in each word:- Convert each
startWordinto a bitmask and store it in a set. - For each
targetWord, remove each letter one at a time and check if the resulting bitmask exists in the set.
- Convert each
Intuition: Instead of trying to go from startWord β targetWord, we reverse the process. We check if removing one letter from targetWord gives us a startWord.
- Algorithm Used: [[Bit_Masking]]
βοΈ Code Implementation (Python)
class Solution:
def wordToMask(self, word: str) -> int:
mask = 0
for ch in word:
mask |= 1 << (ord(ch) - ord('a'))
return mask
def wordCount(self, startWords, targetWords) -> int:
start_set = set()
# Step 1: Convert all startWords to bitmask and store
for word in startWords:
mask = self.wordToMask(word)
start_set.add(mask)
count = 0
# Step 2: For each targetWord, remove each letter and check
for word in targetWords:
target_mask = self.wordToMask(word)
for ch in word:
bit = 1 << (ord(ch) - ord('a'))
reduced_mask = target_mask ^ bit # remove one bit
if reduced_mask in start_set:
count += 1
break # only count once per word
return count
β±οΈ Time & Space Complexity
-
Time:
- O(N * L + M * L) where:
- N = len(startWords)
- M = len(targetWords)
- L = max length of words (<= 26)
Space: O(N) β to store the bitmasks of
startWordsin a set
π§© Key Takeaways
- β Learned how to use bitmasking to represent character sets in a string.
- π‘ Reversing the process (removing a letter from the target) can sometimes simplify the problem.
- π XOR (
^) is a clean and safe way to toggle bits β better than subtraction in bitmask logic.
π Reflection (Self-Check)
- [x] Could I solve this without help? (Eventually, yes)
- [x] Did I write code from scratch?
- [x] Did I understand why it works?
- [x] Will I be able to recall this in a week?
π Related Problems
- [[1717 Maximum Score From Removing Substrings]]
- [[1638 Count Substrings That Differ by One Character]]
π Progress Tracker
| Metric | Value |
|---|---|
| Day | 53 |
| Total Problems Solved | 394 |
| Confidence Today | π |
| Leetcode Rating | 1572 |
Top comments (0)