C++ DFS (3ms) + Memorization with Explanation

  • 1

    We use a hash set to store all visited indices, and we check against the hash set before starting another recursion cycle from the current index of string s. Inside the helper function, if any word can be used to separate string s, we start another recursion cycle from current index+1.

    class Solution {
        bool wordBreak(string s, vector<string>& wordDict) {
            unordered_set<int> visited;
            return helper(s, 0, wordDict, visited);
        bool helper(string s, int start, vector<string>& wordDict, unordered_set<int>& visited) {
            for (string word:wordDict) {
                int index=start+word.size()-1;
                if (index<s.size()) && s.substr(start,word.size())==word) {
                    if (start+word.size()==s.size()) return true;
                    else if (visited.find(index)!=visited.end()) return false;
                    else if (helper(s, index+1, wordDict, visited)) return true;
                    else visited.insert(index);
            return false;

Log in to reply

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