

0131-0140

131. Palindrome Partitioning $\star\star$

class Solution {
 public:
  vector<vector<string>> partition(string s) {
    vector<vector<string>> ans;
    vector<string> path;

    dfs(s, 0, path, ans);

    return ans;
  }

 private:
  void dfs(string& s, int j, vector<string>& path,
           vector<vector<string>>& ans) {
    if (j == s.length()) {
      ans.push_back(path);
      return;
    }

    for (int i = j; i < s.length(); ++i)
      if (isPalindrome(s, j, i)) {
        path.push_back(s.substr(j, i - j + 1));
        dfs(s, i + 1, path, ans);
        path.pop_back();
      }
  }

  bool isPalindrome(string& s, int l, int r) {
    while (l < r)
      if (s[l++] != s[r--]) return false;
    return true;
  }
};

132. Palindrome Partitioning II $\star\star\star$

class Solution {
 public:
  int minCut(string s) {
    const int n = s.length();

    vector<int> cut(n);
    vector<vector<bool>> dp(n, vector<bool>(n));

    for (int i = 0; i < n; ++i) {
      int min = i;
      for (int j = 0; j <= i; ++j)
        if (s[j] == s[i] && (j + 1 > i - 1 || dp[j + 1][i - 1])) {
          dp[j][i] = true;
          min = j == 0 ? 0 : std::min(min, cut[j - 1] + 1);
        }
      cut[i] = min;
    }

    return cut[n - 1];
  }
};

133. Clone Graph $\star\star$

class Solution {
 public:
  Node* cloneGraph(Node* node) {
    if (!node) return NULL;
    if (map.count(node)) return map[node];

    map[node] = new Node(node->val, {});
    for (Node* neighbor : node->neighbors)
      map[node]->neighbors.push_back(cloneGraph(neighbor));

    return map[node];
  }

 private:
  unordered_map<Node*, Node*> map;
};

134. Gas Station $\star\star$

class Solution {
 public:
  int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int ans = 0;
    int net = 0;
    int sum = 0;

    for (int i = 0; i < gas.size(); ++i) {
      net += gas[i] - cost[i];
      sum += gas[i] - cost[i];
      if (sum < 0) {
        sum = 0;
        ans = i + 1;
      }
    }

    return net < 0 ? -1 : ans;
  }
};

135. Candy $\star\star\star$

136. Single Number $\star$

class Solution {
 public:
  int singleNumber(vector<int>& nums) {
    int ans = 0;

    for (int num : nums) ans ^= num;

    return ans;
  }
};

137. Single Number II $\star\star$

class Solution {
 public:
  int singleNumber(vector<int>& nums) {
    int ones = 0;
    int twos = 0;

    for (int num : nums) {
      ones ^= (num & ~twos);
      twos ^= (num & ~ones);
    }

    return ones;
  }
};

138. Copy List with Random Pointer $\star\star$

class Solution {
 public:
  Node* copyRandomList(Node* head) {
    if (!head) return NULL;
    if (map.count(head)) return map[head];

    map[head] = new Node(head->val, NULL, NULL);
    map[head]->next = copyRandomList(head->next);
    map[head]->random = copyRandomList(head->random);

    return map[head];
  }

 private:
  unordered_map<Node*, Node*> map;
};

139. Word Break $\star\star$

class Solution {
 public:
  bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> set(wordDict.begin(), wordDict.end());
    return wordBreak(s, set);
  }

 private:
  unordered_map<string, bool> map;

  bool wordBreak(string& s, unordered_set<string>& set) {
    if (map.count(s)) return map[s];
    if (set.count(s)) return map[s] = true;

    for (int i = 1; i < s.length(); ++i) {
      string left = s.substr(0, i);
      string right = s.substr(i);
      if (wordBreak(left, set) && set.count(right)) return map[s] = true;
    }

    return map[s] = false;
  }
};

140. Word Break II $\star\star\star$

class Solution {
 public:
  vector<string> wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> set(wordDict.begin(), wordDict.end());
    return wordBreak(s, set);
  }

 private:
  unordered_map<string, vector<string>> map;

  vector<string>& wordBreak(string& s, unordered_set<string>& set) {
    if (map.count(s)) return map[s];

    vector<string> ans;

    if (set.count(s)) ans.push_back(s);

    for (int i = 1; i < s.length(); ++i) {
      string right = s.substr(i);
      if (set.count(right)) {
        string left = s.substr(0, i);
        vector<string> leftAns = append(wordBreak(left, set), right);
        ans.insert(ans.end(), leftAns.begin(), leftAns.end());
      }
    }

    return map[s] = ans;
  }

  vector<string> append(vector<string> prefixes, string& word) {
    for (string& prefix : prefixes) prefix += " " + word;
    return prefixes;
  }
};