2135. Count Words Obtained After Adding a Letter LeetCode Solution
In this guide, you will get 2135. Count Words Obtained After Adding a Letter LeetCode Solution with the best time and space complexity. The solution to Count Words Obtained After Adding a Letter problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count Words Obtained After Adding a Letter
You are given two 0-indexed arrays of strings startWords and targetWords. Each string consists of lowercase English letters only.
For each string in targetWords, check if it is possible to choose a string from startWords and perform a conversion operation on it to be equal to that from targetWords.
The conversion operation is described in the following two steps:
Append any lowercase letter that is not present in the string to its end.
For example, if the string is “abc”, the letters ‘d’, ‘e’, or ‘y’ can be added to it, but not ‘a’. If ‘d’ is added, the resulting string will be “abcd”.
Rearrange the letters of the new string in any arbitrary order.
For example, “abcd” can be rearranged to “acbd”, “bacd”, “cbda”, and so on. Note that it can also be rearranged to “abcd” itself.
Return the number of strings in targetWords that can be obtained by performing the operations on any string of startWords.
Note that you will only be verifying if the string in targetWords can be obtained from a string in startWords by performing the operations. The strings in startWords do not actually change during this process.
Example 1:
Input: startWords = [“ant”,”act”,”tack”], targetWords = [“tack”,”act”,”acti”]
Output: 2
Explanation:
– In order to form targetWords[0] = “tack”, we use startWords[1] = “act”, append ‘k’ to it, and rearrange “actk” to “tack”.
– There is no string in startWords that can be used to obtain targetWords[1] = “act”.
Note that “act” does exist in startWords, but we must append one letter to the string before rearranging it.
– In order to form targetWords[2] = “acti”, we use startWords[1] = “act”, append ‘i’ to it, and rearrange “acti” to “acti” itself.
Example 2:
Input: startWords = [“ab”,”a”], targetWords = [“abc”,”abcd”]
Output: 1
Explanation:
– In order to form targetWords[0] = “abc”, we use startWords[0] = “ab”, add ‘c’ to it, and rearrange it to “abc”.
– There is no string in startWords that can be used to obtain targetWords[1] = “abcd”.
Constraints:
1 <= startWords.length, targetWords.length <= 5 * 104
1 <= startWords[i].length, targetWords[j].length <= 26
Each string of startWords and targetWords consists of lowercase English letters only.
No letter occurs more than once in any string of startWords or targetWords.
Complexity Analysis
Time Complexity: O(\Sigma |\texttt{startWords[i]}| + \Sigma |\texttt{targetWords[i]}|)
Space Complexity: O(\Sigma |\texttt{startWords[i]}|)
2135. Count Words Obtained After Adding a Letter LeetCode Solution in C++
class Solution {
public:
int wordCount(vector<string>& startWords, vector<string>& targetWords) {
int ans = 0;
unordered_set<int> seen;
for (const string& w : startWords)
seen.insert(getMask(w));
for (const string& w : targetWords) {
const int mask = getMask(w);
for (const char c : w)
// Toggle one character.
if (seen.contains(mask ^ 1 << c - 'a')) {
++ans;
break;
}
}
return ans;
}
private:
int getMask(const string& s) {
int mask = 0;
for (const char c : s)
mask ^= 1 << c - 'a';
return mask;
}
}; /* code provided by PROGIEZ */
2135. Count Words Obtained After Adding a Letter LeetCode Solution in Java
class Solution {
public int wordCount(String[] startWords, String[] targetWords) {
int ans = 0;
Set<Integer> seen = Arrays.stream(startWords).map(this::getMask).collect(Collectors.toSet());
for (final String w : targetWords) {
final int mask = getMask(w);
for (final char c : w.toCharArray())
// Toggle one character.
if (seen.contains(mask ^ 1 << c - 'a')) {
++ans;
break;
}
}
return ans;
}
private int getMask(final String s) {
int mask = 0;
for (final char c : s.toCharArray())
mask ^= 1 << c - 'a';
return mask;
}
} // code provided by PROGIEZ
2135. Count Words Obtained After Adding a Letter LeetCode Solution in Python
class Solution:
def wordCount(self, startWords: list[str], targetWords: list[str]) -> int:
def getMask(s: str) -> int:
mask = 0
for c in s:
mask ^= 1 << ord(c) - ord('a')
return mask
ans = 0
seen = set(getMask(w) for w in startWords)
for targetWord in targetWords:
mask = getMask(targetWord)
for c in targetWord:
# Toggle one character.
if mask ^ 1 << ord(c) - ord('a') in seen:
ans += 1
break
return ans # code by PROGIEZ
