Count Words Obtained After Adding a Letter

• Initialize a HashSet<String> called startSet.
• Iterate through each word in startWords, sort its characters, and add the resulting string to startSet.
• Initialize a counter count to 0.
• For each word in targetWords:
  • Sort the characters of the word to get sortedTarget.
  • Iterate through each character of sortedTarget.
  • Create a predecessor string by removing the character at the current position.
  • Check if this predecessor string exists in startSet.
  • If it exists, increment count and break the inner loop to process the next targetWord.
• Return the final count.

This approach works by first transforming all startWords into a canonical form and storing them for efficient access. Since the problem allows rearranging letters, sorting the characters of a string provides a suitable canonical representation.

We iterate through startWords, sort each one, and store the result in a HashSet. This set, let's call it startSet, will contain all possible "base" words in their sorted form.

Then, for each targetWord, we want to check if it can be formed by adding a letter to any of the original startWords. This is equivalent to checking if removing one letter from the targetWord results in a string that matches one of the startWords. We apply the same sorting logic to the targetWord. For a given sortedTarget, we generate all possible predecessor strings by removing one character at a time. If any of these predecessors are found in our startSet, it confirms that the targetWord is reachable. We increment our count and, to be efficient, immediately move on to the next targetWord.

1import java.util.Arrays;2import java.util.HashSet;3import java.util.Set;4 5class Solution {6    public int countWords(String[] startWords, String[] targetWords) {7        Set<String> startSet = new HashSet<>();8        for (String word : startWords) {9            char[] chars = word.toCharArray();10            Arrays.sort(chars);11            startSet.add(new String(chars));12        }13 14        int count = 0;15        for (String word : targetWords) {16            char[] chars = word.toCharArray();17            Arrays.sort(chars);18            String sortedTarget = new String(chars);19 20            for (int i = 0; i < sortedTarget.length(); i++) {21                // Create predecessor by removing character at index i22                String predecessor = sortedTarget.substring(0, i) + sortedTarget.substring(i + 1);23                if (startSet.contains(predecessor)) {24                    count++;25                    break; // Found a match, move to the next targetWord26                }27            }28        }29        return count;30    }31}

• Initialize a HashSet<Integer> called startMasks.
• For each word in startWords:
  • Compute its integer bitmask representation.
  • Add the bitmask to startMasks.
• Initialize a counter count to 0.
• For each word in targetWords:
  • Compute its bitmask, targetMask.
  • For each character c in the word:
    • Calculate a predecessorMask by turning off the bit corresponding to c in targetMask.
    • Check if predecessorMask exists in startMasks.
    • If it does, increment count and break to process the next targetWord.
• Return count.

This optimized solution leverages bitmasking to create a unique and efficient integer representation for each word. The presence of each of the 26 lowercase letters is mapped to a bit in an integer.

First, we process all startWords. For each word, we calculate its bitmask by iterating through its characters and setting the corresponding bits. These integer masks are stored in a HashSet for O(1) average time lookups.

Next, we iterate through the targetWords. For each targetWord, we also compute its bitmask. Then, to check if it can be formed from a startWord, we try removing each of its characters one by one. In the bitmask world, removing a character is equivalent to turning off its corresponding bit. We can do this efficiently using the XOR operation (^). For each potential predecessor mask generated, we check if it exists in our set of startWord masks. If a match is found, we increment our count and move to the next targetWord.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int countWords(String[] startWords, String[] targetWords) {6        Set<Integer> startMasks = new HashSet<>();7        for (String word : startWords) {8            startMasks.add(getBitmask(word));9        }10 11        int count = 0;12        for (String word : targetWords) {13            int targetMask = getBitmask(word);14            // Iterate through each character of the target word to find a predecessor15            for (char c : word.toCharArray()) {16                // To remove a character, we turn off its corresponding bit.17                // Using XOR is a neat trick for this since the bit is guaranteed to be set.18                int predecessorMask = targetMask ^ (1 << (c - 'a'));19                if (startMasks.contains(predecessorMask)) {20                    count++;21                    break; // Found a match, move to the next targetWord22                }23            }24        }25        return count;26    }27 28    private int getBitmask(String word) {29        int mask = 0;30        for (char c : word.toCharArray()) {31            mask |= (1 << (c - 'a'));32        }33        return mask;34    }35}