Description

Submission

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        int n = s.length();
        s = '#' + s;
        int states[26][n+1];

        for(int i = 0; i < 26; ++i) {
            states[i][n] = -1;
        }

        for(int i = n - 1; i >= 0; --i) {
            for(int j = 0; j < 26; ++j) {
                states[j][i] = states[j][i+1];
            }
            states[s[i+1]-'a'][i] = i + 1;
        }

        string ret = "";
        for(auto& word: dictionary) {
            int cur = 0;
            for(auto ch: word) {
                cur = states[ch-'a'][cur];
                if(cur == -1) break;
            }
            if(cur != -1) {
                if(word.length() > ret.length() || 
                    (word.length() == ret.length() && word < ret)) {
                        ret = word;
                    }
            }
        }

        return ret;
    }
};