4 ms C++, AC, DP


  • 2
    F

    Implemented an AC solution by DFS first, and then I tried following DP solution.
    I used set instead of array, only record valid indices to set.
    The idea is DP[i] = true if DP[j] = true and s.substr(j, i - j + 1) is in dict, use set to avoid unnecessary iteration.

    It's easy to replace set by array with the same idea, but the array version takes about 40 ms, I have no idea what happened.

    Suppose the output breakSet can be used as graph to generate result for wordBreakII.

    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            unordered_set<int> breakSet;
            breakSet.insert(-1);
            for (int i = 0; i < s.length(); i++) {
                for (unordered_set<int>::iterator it = breakSet.begin(); it != breakSet.end(); it++) {
                    string str = s.substr(*it + 1, i - *it);
                    if (dict.find(str) != dict.end()) {
                        breakSet.insert(i);
                        break;
                    }
                }
            }
            return breakSet.find(s.length() - 1) != breakSet.end();
        }
    };

Log in to reply
 

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