0091-0100

91. Decode Ways $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  int numDecodings(string s) {
    if (s.empty() || s[0] == '0') return 0;
    if (s.length() == 1) return 1;

    int dp1 = 1;
    int dp2 = 1;

    for (int i = 1; i < s.length(); ++i) {
      int dp = 0;
      if (!isValid(s[i]) && !isValid(s[i - 1], s[i])) return 0;
      if (isValid(s[i])) dp += dp1;
      if (isValid(s[i - 1], s[i])) dp += dp2;
      dp2 = dp1;
      dp1 = dp;
    }

    return dp1;
  }

 private:
  bool isValid(char c) { return c != '0'; }
  bool isValid(char c1, char c2) {
    return c1 == '1' || (c1 == '2' && c2 <= '6');
  }
};

92. Reverse Linked List II $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  ListNode* reverseBetween(ListNode* head, int m, int n) {
    if (!head) return NULL;

    ListNode* prev = NULL;
    ListNode* curr = head;

    for (int i = 0; i < m - 1; ++i) {
      prev = curr;
      curr = curr->next;
    }

    ListNode* conn = prev;
    ListNode* tail = curr;

    for (int i = 0; i < n - m + 1; ++i) {
      ListNode* next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
    }

    if (conn)
      conn->next = prev;
    else
      head = prev;
    tail->next = curr;

    return head;
  }
};

93. Restore IP Addresses $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  vector<string> restoreIpAddresses(string s) {
    vector<string> ans;
    vector<string> path(4);

    dfs(s, 0, 0, path, ans);

    return ans;
  }

  void dfs(string s, int depth, int index, vector<string>& path,
           vector<string>& ans) {
    if (depth == 4 && index == s.length()) {
      ans.push_back(path[0] + "." + path[1] + "." + path[2] + "." + path[3]);
      return;
    }
    if (depth == 4 || index == s.length()) return;

    for (int i = 1; i <= 3; ++i) {
      if (index + i > s.length()) return;
      if (i > 1 && s[index] == '0') return;
      string temp = s.substr(index, i);
      if (stoi(temp) > 255) return;
      path[depth] = temp;
      dfs(s, depth + 1, index + i, path, ans);
      path[depth] = "";
    }
  }
};

94. Binary Tree Inorder Traversal $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> stack;
    TreeNode* curr = root;

    while (curr || !stack.empty()) {
      while (curr) {
        stack.push(curr);
        curr = curr->left;
      }
      curr = stack.top();
      stack.pop();
      ans.push_back(curr->val);
      curr = curr->right;
    }

    return ans;
  }
};

95. Unique Binary Search Trees II $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  vector<TreeNode*> generateTrees(int n) {
    if (n == 0) return {};

    return helper(1, n);
  }

 private:
  vector<TreeNode*> helper(int min, int max) {
    vector<TreeNode*> ans;

    if (min > max) {
      ans.push_back(NULL);
      return ans;
    }

    for (int i = min; i <= max; ++i) {
      vector<TreeNode*> leftTree = helper(min, i - 1);
      vector<TreeNode*> rightTree = helper(i + 1, max);
      for (TreeNode* left : leftTree)
        for (TreeNode* right : rightTree) {
          TreeNode* root = new TreeNode(i);
          root->left = left;
          root->right = right;
          ans.push_back(root);
        }
    }

    return ans;
  }
};

96. Unique Binary Search Trees $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  int numTrees(int n) {
    vector<int> G(n + 1);

    G[0] = 1;
    G[1] = 1;

    for (int i = 2; i <= n; ++i)
      for (int j = 0; j < i; ++j) G[i] += G[j] * G[i - j - 1];

    return G[n];
  }
};

97. Interleaving String $\star\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  bool isInterleave(string s1, string s2, string s3) {
    if (s1.length() + s2.length() != s3.length()) return false;

    vector<bool> dp(s2.length() + 1);

    for (int i = 0; i <= s1.length(); ++i)
      for (int j = 0; j <= s2.length(); ++j) {
        if (i == 0 && j == 0)
          dp[j] = true;
        else if (i == 0)
          dp[j] = dp[j - 1] && s2[j - 1] == s3[i + j - 1];
        else if (j == 0)
          dp[j] = dp[j] && s1[i - 1] == s3[i + j - 1];
        else
          dp[j] = (dp[j] && s1[i - 1] == s3[i + j - 1]) ||
                  (dp[j - 1] && s2[j - 1] == s3[i + j - 1]);
      }

    return dp[s2.length()];
  }
};

98. Validate Binary Search Tree $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  bool isValidBST(TreeNode* root) { return helper(root, NULL, NULL); }

 private:
  bool helper(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
    if (!root) return true;
    if (minNode && root->val <= minNode->val ||
        maxNode && root->val >= maxNode->val)
      return false;

    return helper(root->left, minNode, root) &&
           helper(root->right, root, maxNode);
  }
};

99. Recover Binary Search Tree $\star\star\star$

100. Same Tree $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
 public:
  bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p || !q) return p == q;

    return p->val == q->val &&
           isSameTree(p->left, q->left) &&
           isSameTree(p->right, q->right);
  }
};