524. Longest Word in Dictionary through Deleting

/**
 * Pre Processing Time : O(words.length)
 *
 * Time Complexity: O(S.length() + Summation of all chars in all words)
 *
 * Space Complexity: O(words.length)
 */
class Solution {
    class Word {
        String word;
        int index;

        Word(String w) {
            word = w;
            index = 0;
        }
    }

    public String findLongestWord(String s, List<String> d) {
        if (s == null || d == null || s.length() == 0 || d.size() == 0) {
            return "";
        }

        Map<Character, List<Word>> map = new HashMap();
        for (String w : d) {
            if (w.length() > s.length()) {
                continue;
            }
            char c = w.charAt(0);
            if (!map.containsKey(c)) {
                map.put(c, new ArrayList<Word>());
            }
            map.get(c).add(new Word(w));
        }

        String result = "";
        for (char c : s.toCharArray()) {
            if (!map.containsKey(c)) {
                continue;
            }
            List<Word> curBucket = map.get(c);
            map.put(c, new ArrayList<Word>());
            for (Word w : curBucket) {
                w.index++;
                if (w.word.length() == w.index) {
                    if (result.length() < w.word.length()
                            || (result.length() == w.word.length() && w.word.compareTo(result) < 0)) {
                        result = w.word;
                    }
                } else {
                    char nextChar = w.word.charAt(w.index);
                    if (!map.containsKey(nextChar)) {
                        map.put(nextChar, new ArrayList<Word>());
                    }
                    map.get(nextChar).add(w);
                }
            }
        }
        return result;
    }
}

/*
 * Time Complexity: O(N * S)
 *
 * Space Complexity: O(1)
 *
 * N = number of words in the dictionary. S = length of string s.
 */
class Solution {
    public String findLongestWord(String s, List<String> d) {
        if (s == null || d == null || s.length() == 0 || d.size() == 0) {
            return "";
        }

        String result = "";
        for (String word : d) {
            if (word.length() > s.length() || result.length() > word.length()
                    || (result.length() == word.length() && result.compareTo(word) < 0)) {
                continue;
            }
            int indexW = 0;
            for (int indexS = 0; indexS < s.length(); indexS++) {
                if (s.charAt(indexS) == word.charAt(indexW)) {
                    indexW++;
                }
                if (indexW == word.length()) {
                    result = word;
                    break;
                }
            }
        }
        return result;
    }
}