Solution Class Reference

Public Member Functions
bool	wordBreak (string s, vector< string > &wordDict)

Detailed Description

Definition at line 8 of file main.cpp.

Member Function Documentation

wordBreak()

bool Solution::wordBreak ( string  s, vector< string > &  wordDict  )

inline

Definition at line 11 of file main.cpp.

    {
        // array to keep whether s can be segmented at each indices   l e e t c o d e   
        vector<bool> array(s.length() + 1, false); //               1 0 0 0 0 0 0 0 0 
 
        // empty array can always be segmented
        array[0] = true;
        
        for (int i = 0; i <= (int)s.length(); ++i)
        {
            // s[0...i - 1] cannot be segmented
            if (!array[i])
                continue;
 
            // finding all matching words (for input "leetcode", ["leet", "leets", "code"] we would have   l e e t s c o d e)
            for (string& word: wordDict) //                                                              1 0 0 0 1 1 0 0 0 1 
            {
                int end = i + (int)word.length();
                // new valid word is found if whole constructed string is matching a word from dictionary
                if (end <= (int)s.length() && s.substr(i, word.length()) == word)
                    array[end] = true;
            }
        }
 
        // // dp array check
        // for (bool el: array)
        //     cout << el << " ";
        // cout << endl;
 
        return array[s.length()];
    }

Referenced by main().

---

The documentation for this class was generated from the following file:

• main.cpp