[LeetCode] 139. Word Break

• Problem: Word Break
• Concept:
• 可以 recursive 的將一個 word 拆成左半跟右半
• 利用 memorize 的 hash table 來記錄
• 注意終止條件:
• cache 已存在
• 目前的 dictionary 包含完整的 string
• Implementation

• class Solution {
  public:
      bool wordBreak(string s, vector& wordDict) 
      {
          unordered_set quickHash(wordDict.begin(), wordDict.end());
          return wordBreak(s, quickHash);
      }
      
      bool wordBreak(string s, unordered_set quickHash) 
      {
          if (m_mem.count(s)) return m_mem[s];
          if (quickHash.count(s) > 0) {
              m_mem[s] = true;
              return m_mem[s];
          }
  
          for (int i = 1; i < s.length(); i++) {
              if (quickHash.count(s.substr(0, i)) && wordBreak(s.substr(i), quickHash)) {
                  m_mem[s] = true;
                  return m_mem[s];
              }
          }
  
          m_mem[s] = false;
          return m_mem[s];
      }
  
  private:
      unordered_map m_mem;
  };