[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;
  };
  

[LeetCode] 146. LRU Cache

• Problem: 實作 LRU Cache data structure and get/put operations
• Limitation: O(1) time complexity
• Note:
• get 與 put 都包含了 find 的 operation, 若需要 O(1), 則需要 hash table (unordered_map)
• insert 與 pop: 若 insert (push), pop 都是 push / pop back的話, linked list 或是 vector container 都可以達到 O(1) 的 complexity
• move: 但 LRU 包含了將最近使用的 entry 移動到 begin, 這只有 linked list 能達成
• 要明確了解 get/put 的動作, e.g. put 若是 put 同樣 key, 不同 value, 則 value 應更新
• Concept:
• 較無演算發的要求, 畢竟 LRU 本身就是演算法的概念
• 相當於在考 data structure design, 可知要實作 hash table 找 entry (key 做 hash, value 為 pointer to cache entry), 並用 linked list 來maintain cache entries (key, value) 的 pair
• Implementation:

• class LRUCache {
  public:
      LRUCache(int capacity) {
          m_capacity = capacity;
      }   
      
      int get(int key) {
          unordered_map >::iterator>::iterator it = m_hash.find(key);
          if (it != m_hash.cend())
          {   
              // move cache
              m_cache.splice(m_cache.begin(), m_cache, it->second);
              it->second = m_cache.begin();
              return it->second->second;
          }   
          else
              return -1; 
      }   
      
      void put(int key, int value) {
          // 1. find if it alread exists, if yes, move to begin, else insert it
          unordered_map >::iterator>::iterator it = m_hash.find(key);
          if (it != m_hash.cend()) {
              // move cache
              m_cache.splice(m_cache.begin(), m_cache, it->second);
              it->second = m_cache.begin();
              // Note: this value may differ from original one, we need to update value
              it->second->second = value;
          } else {
              // check if size reaches capacity
              if (m_cache.size() >= m_capacity) {
                  // a. remove cache entry
                  it = m_hash.find(m_cache.back().first);
                  //cout << "m_cache.back().first: " << m_cache.back().first << endl;
                  m_hash.erase(it);
                  // b. remove LRU
                  m_cache.pop_back();
              }
              m_cache.emplace(m_cache.begin(), make_pair(key, value));
              m_hash.insert(make_pair(key, m_cache.begin()));
          }
      }
  
  private:
      // O(1) to move, insert, delete nodes, we need list data structure
      // for the given data, we need a pair to store both key & value
      list< pair > m_cache;
  
      // max cache size
      int m_capacity;
  
      // for O(1) to find, we need a hash table which we use map here
      unordered_map >::iterator> m_hash;
  };