LeetCode [320] Generalized Abbreviation

Ref
[1] https://leetcode.com/problems/generalized-abbreviation/

LeetCode [301] Remove Invalid Parentheses

301. Remove Invalid Parentheses

Hard

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

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 33 34 35 36 37 38 39 40 41 42

class Solution { bool isvalid(string s){ int cnt = 0; for(auto c:s){ cnt += c=='('; cnt -= c==')'; if(cnt<0) return false; } return cnt==0; } public: vector<string> removeInvalidParentheses(string s) { int l = 0, r = 0; for(auto c:s){ if(c=='(') l++; else{ if(l==0) r += (c==')'); else l -= (c==')'); } } vector<string> ret; dfs(s, ret, 0, l, r); return ret; } void dfs(string s, vector<string>&ret, int pos, int l, int r){ if(l==0 && r==0 && isvalid(s)){ ret.push_back(s); return; } for(int i=pos; i<s.size(); ++i){ if(i>pos && s[i]==s[i-1]) continue; if(!(s[i]=='(' && l>0 || s[i]==')' && r>0)) continue; string s1 = s; s1.erase(i, 1); if(s[i]=='(' && l>0) dfs(s1, ret, i, l-1, r); else if(s[i]==')' && r>0) dfs(s1, ret, i, l, r-1); } } };

• http://zxi.mytechroad.com/blog/string/leetcode-301-remove-invalid-parentheses/

MJ [44] Find the Longest Substring

Question:
Give a dictionary "dict" and a string "S", find the longest valid word in dict which is a substring of "S".
Eg. dict = {"abc", "defgh", "ef"}
       S = "adbecfgh".
It should return "defgh".

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/32960525.html

LeetCode [294] Flip Game II

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

Example:

Input: s = "++++"
Output: true 
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Follow up:
Derive your algorithm's runtime complexity.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: bool canWin(string s) { int n = s.size(); for(int i=0; i<n-1; ++i){ if(s.substr(i,2)=="++"){ string tmp = s; tmp[i] = '-'; tmp[i+1] = '-'; if (!canWin(tmp)) return true; } } return false; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14

//Java class Solution { public boolean canWin(String s) { int n = s.length(); for(int i=0; i<n-1; ++i){ StringBuilder sb = new StringBuilder(s); if(sb.substring(i, i+2).equals("++")){ sb.replace(i, i+2, "--"); if(!canWin(sb.toString())) return true; } } return false; } }

LeetCode [291] Word Pattern II

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

Example 1:

Input: pattern = "abab", str = "redblueredblue"
Output: true

Example 2:

Input: pattern = pattern = "aaaa", str = "asdasdasdasd"
Output: true

Example 3:

Input: pattern = "aabb", str = "xyzabcxzyabc"
Output: false

Notes:
You may assume both pattern and str contains only lowercase letters.

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 33 34 35

class Solution { public: bool wordPatternMatch(string pattern, string str) { unordered_map<char, string> hash1; unordered_map<string, char> hash2; return bt(pattern, str, 0, 0, pattern.size(), str.size(), hash1, hash2); } bool bt(string &pattern, string &str, int p, int s, int np, int ns, unordered_map<char, string> &hash1, unordered_map<string, char> &hash2){ if(p==np && s==ns){ return true; }else if(p<np && s<ns){ char c = pattern[p]; if(hash1.count(c)){ int len = hash1[c].size(); if(s+len<=ns && str.substr(s, len)==hash1[c] && bt(pattern, str, p+1, s+len, np, ns, hash1, hash2)){ return true; }else{ return false; } }else{ for(int i=s; i<ns; ++i){ string ss = str.substr(s, i-s+1); if(hash2.count(ss)==0){ hash1[c] = ss; hash2[ss] = c; if(bt(pattern, str, p+1, i+1, np, ns, hash1, hash2)) return true; hash2.erase(ss); hash1.erase(c); } } } } return false; } };

MJ [41] Schedule Courses

Question:
schedules gives a number of courses and its possible time slots. Determine if there is a schedule in which all the courses can be arranged without conflicts.
============== =============
Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33021551.html

LeetCode [282] Expression Add Operators

282. Expression Add Operators

Hard

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Example 1:

Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"] 

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]

Example 3:

Input: num = "105", target = 5
Output: ["1*0+5","10-5"]

Example 4:

Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]

Example 5:

Input: num = "3456237490", target = 9191
Output: []

 

Constraints:

• 0 <= num.length <= 10
• num only contain digits.

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 33 34 35 36

typedef long long ll; class Solution { public: vector<string> addOperators(string num, int target) { vector<string> ret; dfs(num, "", 0, 0, 0, ret, target); return ret; } void dfs(string num, string exp, int pos, ll curVal, ll preVal, vector<string>& ret, ll target) { if(pos == num.size() && curVal==target) { ret.push_back(exp); } else if(pos<num.size()) { for(int i=pos; i<num.size(); ++i) { string v = num.substr(pos, i-pos+1); if(v.size()>1 && v[0]=='0') break; if(pos==0) { dfs(num, v, i+1, stoll(v), stoll(v), ret, target); } else { dfs(num, exp+"+"+v, i+1, curVal+stoll(v), stoll(v), ret, target); dfs(num, exp+"-"+v, i+1, curVal-stoll(v), -stoll(v), ret, target); dfs(num, exp+"*"+v, i+1, curVal-preVal+preVal*stoll(v), preVal*stoll(v), ret, target); } } } } };

LeetCode [267] Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

Example 1:

Input: "aabb"
Output: ["abba", "baab"]

Example 2:

Input: "abc"
Output: []

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 33 34 35

class Solution { public: bool wordPatternMatch(string pattern, string str) { unordered_map<char, string> hash1; unordered_map<string, char> hash2; return bt(pattern, str, 0, 0, pattern.size(), str.size(), hash1, hash2); } bool bt(string &pattern, string &str, int p, int s, int np, int ns, unordered_map<char, string> &hash1, unordered_map<string, char> &hash2){ if(p==np && s==ns){ return true; }else if(p<np && s<ns){ char c = pattern[p]; if(hash1.count(c)){ int len = hash1[c].size(); if(s+len<=ns && str.substr(s, len)==hash1[c] && bt(pattern, str, p+1, s+len, np, ns, hash1, hash2)){ return true; }else{ return false; } }else{ for(int i=s; i<ns; ++i){ string ss = str.substr(s, i-s+1); if(hash2.count(ss)==0){ hash1[c] = ss; hash2[ss] = c; if(bt(pattern, str, p+1, i+1, np, ns, hash1, hash2)) return true; hash2.erase(ss); hash1.erase(c); } } } } return false; } };

MJ [17] LED clock

Question:
Consider a LED clock. Eg., 06:30 is displayed by an array of LEDs as 110:11110. Note that the clock only needs 10 LEDs since the maximum hour is 12 (1100) and the maximum minute is 60 (111100). Write program to print all times which turns on n LEDs. 

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33010083.html

LeetCode [279] Perfect Squares

279. Perfect Squares

Medium

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

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 33 34 35 36 37 38 39

class Solution{ public: //bt: TLE int numSquares(int n){ int m = sqrt(n); vector<int> vec(m); for(int i=1; i<=m; ++i){ vec[i-1] = i*i; } int min_sz = INT_MAX; bt(vec, n, min_sz, m, 0, 0, 0); return min_sz; } void bt(vector<int> vec, int target, int &min_sz, int sz, int pos, int cur_sz, int sum){ if(sum==target){ min_sz = min(min_sz, cur_sz); }else if(pos<sz && sum<target && cur_sz<min_sz){ for(int i=pos; i<sz; ++i){ if(sum+vec[i]>target) return; bt(vec, target, min_sz, sz, i, cur_sz+1, sum+vec[i]); } } } //dp: 428 ms int numSquares(int n){ vector<int> dp(n+1); for(int i=0; i<=n; ++i){ dp[i] = i; if(i>3){ int r = sqrt(i); for(int j = r; j>=1; --j){ dp[i] = min(dp[i], 1+dp[i-j*j]); } } } return dp[n]; } };

1 2 3 4 5 6 7 8 9 10 11 12

class Solution { public int numSquares(int n) { int[] dp = new int[n+1]; for(int i=1; i<=n; ++i){ dp[i] = Integer.MAX_VALUE; for(int j=1; j*j<=i; ++j){ dp[i] = Math.min(dp[i], 1+dp[i-j*j]); } } return dp[n]; } }

LeetCode [254] Factor Combinations

Ref
[1] https://leetcode.com/problems/factor-combinations/
OJ

LeetCode [216] Combination Sum III

 216. Combination Sum III

Medium

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

• Only numbers 1 through 9 are used.
• Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

 

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations. [1,2,1] is not valid because 1 is used twice.

Example 4:

Input: k = 3, n = 2
Output: []
Explanation: There are no valid combinations.

Example 5:

Input: k = 9, n = 45
Output: [[1,2,3,4,5,6,7,8,9]]
Explanation:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
​​​​​​​There are no other valid combinations.

 

Constraints:

• 2 <= k <= 9
• 1 <= n <= 60

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<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> res; vector<int> cur; bt(k, n, res, cur, 1, 0); return res; } void bt(int k, int n, vector<vector<int>> &res, vector<int> cur, int pos, int sum){ if(sum==n && cur.size()==k){ res.push_back(cur); }else if(sum<n && pos<=9 && cur.size()<k){ for(int i=pos; i<=9; ++i){ if(sum+i>n) return; cur.push_back(i); bt(k, n, res, cur, i+1, sum+i); cur.pop_back(); } } } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { List<List<Integer>> lists = new ArrayList<>(); public List<List<Integer>> combinationSum3(int k, int n) { helper(0, new ArrayList<>(), k, n, 1); return lists; } void helper(int sum, List<Integer> list, int k, int n, int p){ if(sum>=n){ if(sum==n && list.size()==k){ lists.add(list); } }else if(p<=9 && sum+p<=n && list.size()<k){ helper(sum, list, k, n, p+1); List<Integer> newList = new ArrayList<Integer>(list); newList.add(p); helper(sum+p, newList, k, n, p+1); } } }