https://www.lintcode.com/problem/find-words

FindWord.java

public class Solution {
    /**
     * @param str: the string
     * @param dict: the dictionary
     * @return: return words which  are subsequences of the string
     */
    public List<String> findWords(String str, List<String> dict) {
        // Write your code here.
        List<String> words = new LinkedList<>();
        if (str == null || str.length() < 1 || dict == null || dict.size() < 1) {
            return words;
        }
        
        int[][] nextCharIndex = getNextCharIndex(str);
        for (String word : dict) {
            if (containsWord(nextCharIndex, word)) {
                words.add(word);
            }
        }
        return words;
    }
    
    private int[][] getNextCharIndex(String str) {
        int len = str.length();
        int[][] nextCharIndex = new int[len + 1][26];
    
        for (int i = 0; i < 26; i++) {
            nextCharIndex[len][i] = len;
        }
        
        for (int i = len - 1; i >= 0; i--) {
            for(int charIndex = 0; charIndex < 26; charIndex++) {
                nextCharIndex[i][charIndex] = nextCharIndex[i + 1][charIndex];
            }
            nextCharIndex[i][str.charAt(i) - 'a'] = i;
        }
        return nextCharIndex;
    }
    
    private boolean containsWord(int[][] nextCharIndex, String word) {
        int strIndex = 0;
        int wordIndex = 0;
        int strLen = nextCharIndex.length - 1;
        int wordLen = word.length();
        
        while (strIndex < strLen && wordIndex < wordLen) {
            int charIndex = word.charAt(wordIndex) - 'a';
            strIndex = nextCharIndex[strIndex][charIndex];
            if (strIndex >= strLen) {
                return false;
            }
            strIndex++;
            wordIndex++;
        }
        
        return wordIndex >= wordLen;
    }
}