

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$

func wordBreak(s string, wordDict []string) bool {
    // return func1(s, wordDict);
    // return func2(s, 0, len(s)-1, wordDict);
    // return func3(s, wordDict);
    // return func4(s, wordDict);
    // return func5(s, wordDict);
    // return func6(s, wordDict);
    // return func7(s, wordDict);
    // return func8(s, wordDict);
    return func9(s, wordDict);
}

// 1. recursive
func func1(s string, wordDict []string) bool {
    if len(s) == 0 {
        return true;
    }
    for pos := 0; pos <= len(s); pos++ {
        for _, word := range wordDict {
            if s[0:pos] == word && func1(s[pos:], wordDict) {
                return true;
            }
        }
    }
    return false;
}

// 2. recursive + string-optimize
func func2(s string, lo int, hi int, wordDict []string) bool {
    if (lo > hi) {
        return true;
    }

    for pos := lo; pos <= hi; pos++ {
        for _, word := range wordDict {
            if strCompHelper(s, lo, pos, word) && func2(s, pos+1, hi, wordDict) {
                return true;
            }
        }
    }

    return false;
}

// 3. recursive + string-optimize + memo
func func3(s string, wordDict []string) bool {
    N := len(s);
    // 0=init, 1=false, 2=true
    memo := make([][]int, N);
    for i := 0; i < N; i++ {
        memo[i] = make([]int, N);
    }
    return helper3(s, 0, N-1, wordDict, memo);
}
func helper3(s string, lo int, hi int, wordDict []string, memo [][]int ) bool {
    if (lo > hi) {
        return true;
    }
    if memo[lo][hi] == 1 {
        return false;
    } else if memo[lo][hi] == 2 {
        return true;
    }

    for pos := lo; pos <= hi; pos++ {
        for _, word := range wordDict {
            if strCompHelper(s, lo, pos, word) && helper3(s, pos+1, hi, wordDict, memo) {
                memo[lo][hi] = 2;
                return true;
            }
        }
    }
    memo[lo][hi] = 1;
    return false;
}

// 4. recursive + string-optimize + memo + use-map-instead-of-array
func func4(s string, wordDict []string) bool {
    N := len(s);
    // 0=init, 1=false, 2=true
    memo := make([][]int, N);
    for i := 0; i < N; i++ {
        memo[i] = make([]int, N);
    }
    wordMap := make(map[string]bool);
    for i:= 0; i < len(wordDict); i++ {
        wordMap[wordDict[i]] = true;
    }

    return helper4(s, 0, N-1, wordMap, memo);
}
func helper4(s string, lo int, hi int, wordMap map[string]bool, memo [][]int) bool {
    if (lo > hi) {
        return true;
    }
    if memo[lo][hi] == 1 {
        return false;
    } else if memo[lo][hi] == 2 {
        return true;
    }

    for pos := lo; pos <= hi; pos++ {
        if _, ok := wordMap[s[lo:pos+1]]; ok {
            if helper4(s, pos+1, hi, wordMap, memo) {
                memo[lo][hi] = 2;
                return true;
            }
        }
    }
    memo[lo][hi] = 1;
    return false;
}

// 5. iterative 2D + string-optimize + use-map-instead-of-array
// !!ERROR, can't guarantee when calculate m[i][j] already got
// m[i][k]...m[k+1][j]
func func5(s string, wordDict []string) bool {
    N := len(s);
    memo := make([][]bool, N);
    for i := 0; i < N; i++ {
        memo[i] = make([]bool, N);
    }
    wordMap := make(map[string]bool);
    for i:= 0; i < len(wordDict); i++ {
        wordMap[wordDict[i]] = true;
    }
    for i := 0; i < N; i++ {
        for j := i; j < N; j++ {
            if _, ok := wordMap[s[i:j+1]]; ok {
                memo[i][j] = true;
                continue;
            }
            for k := i; k < j; k++ {
                if memo[i][k] && memo[k+1][j] {
                    memo[i][j] = true;
                    break;
                }
            }
        }
    }
    return memo[N-1][N-1];
}

// 6. iterative 2D + string-optimize + use-map-instead-of-array
// Use substring size iterate 1,2,3..., O(n^3) time 
func func6(s string, wordDict []string) bool {
    N := len(s);
    memo := make([][]bool, N);
    for i := 0; i < N; i++ {
        memo[i] = make([]bool, N);
    }
    wordMap := make(map[string]bool);
    for i:= 0; i < len(wordDict); i++ {
        wordMap[wordDict[i]] = true;
    }

    // size == 1
    for i := 0; i < N; i++ {
        if _, ok := wordMap[s[i:i+1]]; ok {
            memo[i][i] = true;
        }
    }
    // size >= 2
    for sz := 2; sz <= N; sz++ {
        for lo, hi := 0, sz-1; hi < N; lo, hi = lo+1, hi+1 {
            if _, ok := wordMap[s[lo:hi+1]]; ok {
                memo[lo][hi] = true;
                continue;
            }
            for mid := lo; mid < hi; mid++ {
                if memo[lo][mid] && memo[mid+1][hi] {
                    memo[lo][hi] = true;
                    break;
                }
            }
        }
    }

    return memo[0][N-1]; 
}

// 7. A different thought, F[0...n] = F[0...x] && isWord(x+1..n)
// recursive solution
func func7(s string, wordDict []string) bool {
    N := len(s)
    wordMap := make(map[string]bool);
    for i:= 0; i < len(wordDict); i++ {
        wordMap[wordDict[i]] = true;
    }

    return helper7(s, N-1, wordMap);
}
func helper7(s string, end int, wordMap map[string]bool) bool {
    if end < 0 {
        return true;
    }

    for i := end; i >= 0; i-- {
        if _, ok := wordMap[s[i:end+1]]; ok {
            if helper7(s, i-1, wordMap) {
                return true;
            }
        }
    }

    return false;
}

// 8. same 7, but with memo
func func8(s string, wordDict []string) bool {
    N := len(s)
    // 0=init, 1=false, 2=true
    memo := make([]int, N);
    wordMap := make(map[string]bool);
    for i := 0; i < len(wordDict); i++ {
        wordMap[wordDict[i]] = true;
    }

    return helper8(s, N-1, wordMap, memo);
}
func helper8(s string, end int, wordMap map[string]bool, memo []int) bool {
    if end < 0 {
        return true;
    }
    if memo[end] != 0 {
        return memo[end] == 2;
    }
    for i := end; i >= 0; i-- {
        if _, ok := wordMap[s[i:end+1]]; ok {
            if helper8(s, i-1, wordMap, memo) {
                memo[end] = 2;
                return true;
            }
        }
    }
    memo[end] = 1;
    return false;
}

// 9. same 7, finially, bottom-up, 1D, O(n^2) solution
func func9(s string, wordDict []string) bool {
    N := len(s)
    memo := make([]bool, N);
    wordMap := make(map[string]bool);
    for i := 0; i < len(wordDict); i++ {
        wordMap[wordDict[i]] = true;
    }

    for i := 0; i < N; i++ {
        if _, ok := wordMap[s[0:i+1]]; ok {
            memo[i] = true;
            continue;
        }
        for j := i; j >= 0; j-- {
            if _, ok := wordMap[s[j:i+1]]; ok && memo[j-1] {
                memo[i] = true;
                break;
            }
        }
    }

    return memo[N-1];
}

func strCompHelper(s string, lo int, hi int, word string) bool {
    m := hi - lo + 1;
    n := len(word);
    if m != n {
        return false;
    }

    for i := lo; i <= hi; i++ {
        if s[i] != word[i-lo] {
            return false;
        }
    }

    return true;
}

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