[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] 50 power (x, n)

• Problem: power (x, n), x為正整數
• Solution:
• 一種是 iteratively 的用 while loop, count down n 的值, 每次乘上 x
• 另一種直覺的是用 recursive, 但注意指數可以用平方來加速, 即 x^2 = x * x
• Note: 注意各 boundary, e.g. n < 0, n = MIN_INT 及 unsigned/signed 切換等 case

class Solution {
public:
    double myPow(double x, int n) {
        if (0 == n) return 1;
        if (1 == n) return x;

        double sq = myPow(x, n/2);
        if (INT_MIN == n)
            return sq * sq;
        if (0 > n) return 1.0 / myPow(x, abs((unsigned int)-n));

        if (0 == n % 2)
            return sq * sq;
        else
            return x * sq * sq;
    }
};

[LeetCode] 21 Merge Two Sorted Lists

• Problem: merge 兩個已排序的 lists
• Solution: 
• 可以直接 iteratively 比較兩個 list 元素, 一個一個 push
• recursive
• 終止條件: list0 或 list1已到結尾, 則 return 另一個 list
• 當前判斷:
• 將最小元素的 next 指向 recursive return 回來的 list
• Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (NULL == l1) return l2;
        if (NULL == l2) return l1;
        
        if (l1->val < l2->val) 
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
            
    }
};

[LeetCode] 22. generate parentheses

• Problem: 給定括號個數, 產生合法的括號排列組合
• Solution:
• 以 recursive 方式來解決
• 當下考慮的是, 還要加入幾個左括號及幾個右括號
• 終止條件: 左右括號都加完了
• 當前條件: 左括號沒有限制, 右括號則需有對應的左括號先加入了才行
• Note: 注意邊際條件 leftCount > 0
• Code

class Solution {
public:
    // recursive solve this problem
    static void genParenthesis(vector &result, string s, int leftCount, int rightCount) {
        // when append done, add string to vector
        if (0 == leftCount && 0 == rightCount)
            result.push_back(s);

        // no matter where position, if leftCount > 0, you can add it
        if (leftCount > 0) 
            genParenthesis(result, s + "(", leftCount - 1, rightCount); 

        // you can append right parenthesis only when rightCount > leftCount
        if (leftCount < rightCount)
            genParenthesis(result, s + ")", leftCount, rightCount - 1);
    }
    
    vector generateParenthesis(int n) {
        vector result;
        genParenthesis(result, "", n, n);
        return result;
    }
};

[Programming] Recursive

• Programming problems 中重要的一個分類就是 recursive
• e.g. 著名的 n 階算法
int factorial(int n) { if (1 == n) return 1; if (0 == n) return 1; return n * factorial(n-1); }
• 但更重要的是應該要考慮 recursive 的限制
• stack overflow
• 解法: 
• tail recursive
• 連結內的解釋相當清楚, 主要是透過寫法不同, 讓 compiler 在 O2, O3的 optimization時, 不用 call function, 而是 jne (jump not equal)

• int factorial_acc(int n, int acc = 1) 
  {    
      if (n == 1) 
          return acc;
      else
          return factorial_acc(n - 1, n * acc);
  }
  

• iterative

• int factorial_iterative(int n)
  {
      int acc = 1;
      if (n <= 1) return acc;
      while (n > 1)
      {
          acc *= n;
          n--;
      }
      return sum;
  }

• 延伸閱讀
• Iterative vs. Recursive
• Stack size
• stack vs heap