Method 1 - Character Frequency Comparison

Intuition

A step word must have exactly one more character than the input word, and all characters from the input word must be present in the step word. We can verify this by comparing character frequencies - the step word should have exactly the same frequency for each character as the input word, except for one additional character.

Approach

For each word in the dictionary, check if its length is exactly one more than the input word
Count character frequencies for both the input word and dictionary word
Check if the dictionary word contains all characters from input word with same frequencies
Verify that exactly one additional character is present in the dictionary word
If all conditions are met, add the word to the result

Code

[{"language":"C++","code":"class Solution {\npublic:\n    vector<string> findStepWords(string word, vector<string>& dictionary) {\n        vector<string> result;\n        unordered_map<char, int> wordFreq = getFrequency(word);\n        \n        for (const string& dictWord : dictionary) {\n            if (dictWord.length() != word.length() + 1) continue;\n            \n            if (isStepWord(wordFreq, dictWord)) {\n                result.push_back(dictWord);\n            }\n        }\n        \n        return result;\n    }\n    \nprivate:\n    unordered_map<char, int> getFrequency(const string& s) {\n        unordered_map<char, int> freq;\n        for (char c : s) {\n            freq[c]++;\n        }\n        return freq;\n    }\n    \n    bool isStepWord(const unordered_map<char, int>& wordFreq, const string& dictWord) {\n        unordered_map<char, int> dictFreq = getFrequency(dictWord);\n        int extraChars = 0;\n        \n        // Check each character in dictionary word\n        for (const auto& pair : dictFreq) {\n            char c = pair.first;\n            int count = pair.second;\n            \n            if (wordFreq.count(c)) {\n                if (count < wordFreq.at(c)) return false;\n                extraChars += count - wordFreq.at(c);\n            } else {\n                extraChars += count;\n            }\n        }\n        \n        return extraChars == 1;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func findStepWords(word string, dictionary []string) []string {\n    var result []string\n    wordFreq := getFrequency(word)\n    \n    for _, dictWord := range dictionary {\n        if len(dictWord) != len(word)+1 {\n            continue\n        }\n        \n        if isStepWord(wordFreq, dictWord) {\n            result = append(result, dictWord)\n        }\n    }\n    \n    return result\n}\n\nfunc getFrequency(s string) map[rune]int {\n    freq := make(map[rune]int)\n    for _, c := range s {\n        freq[c]++\n    }\n    return freq\n}\n\nfunc isStepWord(wordFreq map[rune]int, dictWord string) bool {\n    dictFreq := getFrequency(dictWord)\n    extraChars := 0\n    \n    for c, count := range dictFreq {\n        if originalCount, exists := wordFreq[c]; exists {\n            if count < originalCount {\n                return false\n            }\n            extraChars += count - originalCount\n        } else {\n            extraChars += count\n        }\n    }\n    \n    return extraChars == 1\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public List<String> findStepWords(String word, String[] dictionary) {\n        List<String> result = new ArrayList<>();\n        Map<Character, Integer> wordFreq = getFrequency(word);\n        \n        for (String dictWord : dictionary) {\n            if (dictWord.length() != word.length() + 1) continue;\n            \n            if (isStepWord(wordFreq, dictWord)) {\n                result.add(dictWord);\n            }\n        }\n        \n        return result;\n    }\n    \n    private Map<Character, Integer> g

Related Tags