Problem

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:

  1. 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".
  1. 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 _thenumber of strings in _targetWords _that can be obtained by performing the operations onany 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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5

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 * 10^4
  • 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.

Solution

Method 1 – Bitmask Hashing

Intuition

The key idea is to represent each word as a bitmask, where each bit corresponds to a letter. For each target word, we can remove one letter at a time and check if the resulting bitmask exists in the set of start word bitmasks. This is efficient because all words have unique letters and are at most 26 characters long.

Approach

  1. Convert each word in startWords to a bitmask and store in a set.
  2. For each word in targetWords:
    • Convert it to a bitmask.
    • For each letter in the word, remove that letter (by toggling its bit off) and check if the resulting bitmask exists in the set.
    • If any such bitmask exists, increment the answer.
  3. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int wordCount(vector<string>& startWords, vector<string>& targetWords) {
        unordered_set<int> s;
        for (auto& w : startWords) {
            int mask = 0;
            for (char c : w) mask |= 1 << (c - 'a');
            s.insert(mask);
        }
        int ans = 0;
        for (auto& w : targetWords) {
            int mask = 0;
            for (char c : w) mask |= 1 << (c - 'a');
            for (char c : w) {
                int m2 = mask ^ (1 << (c - 'a'));
                if (s.count(m2)) {
                    ++ans;
                    break;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func wordCount(startWords []string, targetWords []string) int {
    s := make(map[int]struct{})
    for _, w := range startWords {
        mask := 0
        for _, c := range w {
            mask |= 1 << (c - 'a')
        }
        s[mask] = struct{}{}
    }
    ans := 0
    for _, w := range targetWords {
        mask := 0
        for _, c := range w {
            mask |= 1 << (c - 'a')
        }
        for _, c := range w {
            m2 := mask ^ (1 << (c - 'a'))
            if _, ok := s[m2]; ok {
                ans++
                break
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int wordCount(String[] startWords, String[] targetWords) {
        Set<Integer> s = new HashSet<>();
        for (String w : startWords) {
            int mask = 0;
            for (char c : w.toCharArray()) mask |= 1 << (c - 'a');
            s.add(mask);
        }
        int ans = 0;
        for (String w : targetWords) {
            int mask = 0;
            for (char c : w.toCharArray()) mask |= 1 << (c - 'a');
            for (char c : w.toCharArray()) {
                int m2 = mask ^ (1 << (c - 'a'));
                if (s.contains(m2)) {
                    ans++;
                    break;
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun wordCount(startWords: Array<String>, targetWords: Array<String>): Int {
        val s = mutableSetOf<Int>()
        for (w in startWords) {
            var mask = 0
            for (c in w) mask = mask or (1 shl (c - 'a'))
            s.add(mask)
        }
        var ans = 0
        for (w in targetWords) {
            var mask = 0
            for (c in w) mask = mask or (1 shl (c - 'a'))
            for (c in w) {
                val m2 = mask xor (1 shl (c - 'a'))
                if (m2 in s) {
                    ans++
                    break
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def wordCount(self, startWords: list[str], targetWords: list[str]) -> int:
        s = set()
        for w in startWords:
            mask = 0
            for c in w:
                mask |= 1 << (ord(c) - ord('a'))
            s.add(mask)
        ans = 0
        for w in targetWords:
            mask = 0
            for c in w:
                mask |= 1 << (ord(c) - ord('a'))
            for c in w:
                m2 = mask ^ (1 << (ord(c) - ord('a')))
                if m2 in s:
                    ans += 1
                    break
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

impl Solution {
    pub fn word_count(start_words: Vec<String>, target_words: Vec<String>) -> i32 {
        let mut s = std::collections::HashSet::new();
        for w in start_words.iter() {
            let mut mask = 0;
            for c in w.chars() {
                mask |= 1 << (c as u8 - b'a');
            }
            s.insert(mask);
        }
        let mut ans = 0;
        for w in target_words.iter() {
            let mut mask = 0;
            for c in w.chars() {
                mask |= 1 << (c as u8 - b'a');
            }
            for c in w.chars() {
                let m2 = mask ^ (1 << (c as u8 - b'a'));
                if s.contains(&m2) {
                    ans += 1;
                    break;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    wordCount(startWords: string[], targetWords: string[]): number {
        const s = new Set<number>();
        for (const w of startWords) {
            let mask = 0;
            for (const c of w) mask |= 1 << (c.charCodeAt(0) - 97);
            s.add(mask);
        }
        let ans = 0;
        for (const w of targetWords) {
            let mask = 0;
            for (const c of w) mask |= 1 << (c.charCodeAt(0) - 97);
            for (const c of w) {
                const m2 = mask ^ (1 << (c.charCodeAt(0) - 97));
                if (s.has(m2)) {
                    ans++;
                    break;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(N * L + M * L), where N is the number of startWords, M is the number of targetWords, and L is the max word length (≤26).
  • 🧺 Space complexity: O(N), for the set of startWords bitmasks.