25 Lines Concise & Clear & Clean C++; Not Using Trie or Hash For Greatest Simplicity


  • 0
    F

    Not the fastest, but probably the cleanest and easiest implementation.

    class Solution {
        vector<string> words, result;
        vector<vector<string>> results;
        void solve(vector<string>::iterator liter, vector<string>::iterator riter) 
        {
            if (result.size() == words[0].size())
                return results.push_back(result);
            for (auto iter = liter; iter < riter; ++ iter)
            {
                const string & str = *iter;
                result.push_back(str);
                string prefix;
                for (auto str : result)
                    prefix += str[result.size()];
                auto new_liter = lower_bound(words.begin(), words.end(), prefix);
                prefix.back() += 1;
                auto new_riter = lower_bound(words.begin(), words.end(), prefix);
                solve(new_liter, new_riter);
                result.pop_back();
            }
        }
    public:
        vector<vector<string>> wordSquares(vector<string>& w) {
            words = std::move(w);
            sort(words.begin(), words.end());
            solve(words.begin(), words.end());
            return results;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.