C++, 3ms solution with vector for dictionary


  • 0
    S
    bool wordBreak(string s, vector<string>& wordDict) {
        
        stack<int> st;
        st.push(0);
        
        vector<bool> visited(s.size() + 1, false);
        
        while (!st.empty())
        {
            int cur = st.top();
            st.pop();
            
            if (cur == s.size())
                return true;
            
            for (const string& w : wordDict)
            {
                const int i = cur + w.size();
                if (i >= visited.size() || visited[cur + w.size()])
                    continue;
                    
                if (!strncmp(w.c_str(), s.c_str() + cur, w.size()))
                {
                    visited[i] = true;
                    st.push(cur + w.size());
                }
            }
        }
        
        return false;
    }

Log in to reply
 

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