[LeetCode]: 546. Remove Boxes

https://leetcode.com/contest/leetcode-weekly-contest-25/problems/remove-boxes/

Solution:
This question is not easy. May use the dsf strategy, but the brutal force one cannot pass the OJ. One way to optimize it is to use memorization of the intermediate states. The parameters for the states needs include the range, the number of repeated elements, and the earned points. The range needs two parameters: the left and right. So we need a three-dimensional array to represent the states, and the value of it will be earned points. Let us dp[l][r][ct] represent the highest points earned in the range of l to r, where l is the left boundary, r is the right boundary, and ct is the number of repeated elements. The we need to calculate dp[0][n-1][0].

We can first calculate the dp[l][r][ct] = dsf(l+1, r, 0) + (ct+1)*(ct+1), which is equivalent to separate the original array into the first element and the rest ones;
Then is the key part:  since we need to find the maximum, we need to loop the whole array, and when the same elements as the first element is found, the transition equation can be wrote:
                 dp[l][r][ct] = max(dp[l][r][ct], dsf(l+1, i-1, 0) + dsf(i, r, ct+1)),  when arr[l] == arr[i].
where i is between l+1 and r. The second term in the max() is to divide the array into two parts: the first one is from l+1 to i-1 with 0 repeated elements; the other is from i to r with ct+1 repeated elements so far (arr[l] == arr[i]). (or the l element is now adjacent with the ith element.)

In order to reduce the complexity of the dsf, we can assign some unique initial value to dp[l][r][ct], for example, a negative value. Then when the dp[l][r][ct] becomes positive, it means it has already been calculated. So we can just use the calculated results directly. This is exactly how memorization works. See code below for details:

Code:

const int N = 100;
int dp[N][N][N];

class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        int n = boxes.size();
        memset(dp, -1, sizeof(dp));
        return dsf(boxes, 0, n-1, 0);
    }

    int dsf(vector<int> &b, int l, int r, int ct){
        if(l>r) return 0;
        int t = dp[l][r][ct];
        if(t!=-1) return t;
        t = dsf(b, l+1, r, 0) + (ct+1)*(ct+1);
        for(int i=l+1; i<=r; ++i){
            if(b[i]==b[l]) t=max(t, dsf(b, l+1, i-1, 0) + dsf(b, i, r, ct+1));
        }
        return dp[l][r][ct]=t;
    }
};

[LeetCode] 499. The Maze II

https://leetcode.com/contest/leetcode-weekly-contest-17/problems/the-maze-ii/

Solution:
will use DSF strategy. Use a bool flag to represent the status of the ball, true for stop and false for moving. The reason for distinguishing these two is that once it stops, it can move all the directions (if OK); but once it moves, it can only goes one direction (recorded in the trace string) until hits on the wall. And once the ball hits on the wall, there will be a switch between stop and move. In order to avoid duplicates, a visit vector is used to trace the visiting status of the ball positions only when it stops. For the smallest path, we will trace the steps needed. Once find the steps needed are larger than the one that have already been found, the recursion can return since it is not necessary. 

Code:

class Solution {
public:
    string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
        vector<string> ss;
        string s;
        vector<vector<bool>> visit(maze.size(), vector<bool>(maze.front().size(), true));
//label only when stop;
        visit[ball[0]][ball[1]] = false;
        int step = 0, l = 0;
        bool flag = true;//stop;
        findDSF(maze, ball[0], ball[1], hole, visit, s, ss, step, l, flag);
        if(ss.empty()) return "impossible";
        sort(ss.begin(), ss.end());
        return ss[0];
    }
private:
    void findDSF(vector<vector<int>> &m, int x, int y, vector<int> &h, vector<vector<bool>> &v, 
string s, vector<string> &ss, int step, int &l, bool flag){
        if(ss.size()&&step>l) return;//if more step needed, can give up;
        if(x==h[0] && y==h[1]){
            if(ss.empty() || step == l){ ss.push_back(s); l = step;}
            else{
                if(step<l){ ss.clear(); ss.push_back(s); l = step;}
            }
            return;
        }
        if(flag){//ball stops now, and is going to move;
            if(x-1>=0&&!m[x-1][y]&&v[x-1][y]){
                flag = false;
                if(x-1==0||(x-1>0&&m[x-2][y])) {flag = true;v[x-1][y] = false;}
                findDSF(m, x-1, y, h, v, s+'u', ss, step+1, l, flag);
                v[x-1][y] = true;
                flag = true;
            }
            if(x+1<m.size()&&!m[x+1][y]&&v[x+1][y]){
                flag = false;
                if(x+1==m.size()-1||(x+1<m.size()-1&&m[x+2][y])) 
                    {flag = true;v[x+1][y] = false;}
                findDSF(m, x+1, y, h, v, s+'d', ss, step+1, l, flag);
                v[x+1][y] = true;
                flag = true;
            }
            if(y+1<m.front().size()&&!m[x][y+1]&&v[x][y+1]){
                flag = false;
                if((y+1==m.front().size()-1)||(y+1<m.front().size()-1&&m[x][y+2])) 
                    {flag=true;v[x][y+1]=false;}
                findDSF(m, x, y+1, h, v, s+'r', ss, step+1, l, flag);
                v[x][y+1] = true;
                flag = true;
            }
           if(y-1>=0&&!m[x][y-1]&&v[x][y-1]){
                flag = false;
                if((y-1==0)||(y-1>0&&m[x][y-2])) {flag = true;v[x][y-1] = false;}
                findDSF(m, x, y-1, h, v, s+'l', ss, step+1, l, flag);
                v[x][y-1] = true;
                flag = true;
            }
        }
        else{//ball is moving, and it may stop when hits on the wall;
            if(s.back()=='u'&&x-1>=0&&!m[x-1][y]&&v[x-1][y]){
                if(x-1==0||(x-1>0&&m[x-2][y])) {flag = true;v[x-1][y] = false;}
                findDSF(m, x-1, y, h, v, s, ss, step+1, l, flag);
                v[x-1][y] = true;
                flag = false;
            }
            else if(s.back()=='d'&&x+1<m.size()&&!m[x+1][y]&&v[x+1][y]){
                if(x+1==m.size()-1||(x+1<m.size()-1&&m[x+2][y])) 
                    {flag = true;v[x+1][y] = false;}
                findDSF(m, x+1, y, h, v, s, ss, step+1, l, flag);
                v[x+1][y] = true;
                flag = false;
            }
            else if(s.back()=='r'&&y+1<m.front().size()&&!m[x][y+1]&&v[x][y+1]){
                if(y+1==m.front().size()-1||(y+1<m.front().size()-1&&m[x][y+2])) 
                    {flag = true;v[x][y+1]=false;}
                findDSF(m, x, y+1, h, v, s, ss, step+1, l, flag);
                v[x][y+1] = true;
                flag = false;
            }
            else if(s.back() =='l'&&y-1>=0&&!m[x][y-1]&&v[x][y-1]){
                if(y-1==0||(y-1>0&&m[x][y-2])) {flag = true;v[x][y-1] = false;}
                findDSF(m, x, y-1, h, v, s, ss, step+1, l, flag);
                v[x][y-1] = true;
                flag = false;
            }
            else return;
        }
    }
};

The code length is too long for DSF, and it should be shorter if using BSF. But we need to trace the path and steps too. So we need some data structure to connect the positions with the steps and paths. Pair structure (pair<int, string> is chosen for step and path, and positions can be represented by a two dimensional array. So the data structure overall looks like this: vector<vector<pair<int, string>>>.  The code below is based on BSF strategy.

Code:

class Solution {
public:
    string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
        pair<int, string> dp[30][30];
        int n=maze.size(), m=maze[0].size();
        for(int i=0;i<n;i++)for(int j=0;j<m;j++) dp[i][j]=make_pair(10000000,"");
        vector<int> dx={1, 0, 0, -1};
        vector<int> dy={0, -1, 1, 0};
        string c="dlru"; 
        queue<pair<int,int>> q;
        q.push(make_pair(ball[0],ball[1]));
        dp[ball[0]][ball[1]]=make_pair(0,"");
        while(q.size()){
            pair<int, int> t=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                pair<int, int> now=t;
                int v=0;
                while(1){
                    if(now.first==hole[0]&&now.second==hole[1])break;
                    pair<int, int> next=make_pair(now.first+dx[i],now.second+dy[i]);
                    if(next.first<0||next.second<0||next.first>=n||next.second>=m)break;
                    if(maze[next.first][next.second]==1)break;
                    v++;
                    now=next;
                }
                pair<int, string>tt=make_pair(dp[t.first][t.second].first+v,dp[t.first][t.second].second+c[i]);
                if(v&&dp[now.first][now.second]>tt){
                    dp[now.first][now.second]=tt;
                    q.push(now);
                }
            }
        }
        if(dp[hole[0]][hole[1]].first==10000000)return "impossible";
        return dp[hole[0]][hole[1]].second;
    }
};

[LeetCode] 464. Can I Win

https://leetcode.com/problems/can-i-win/


Solution:
One of the important constrains is that each element can only be used once. Therefore, if we use dp strategy, we have to take it into account since it will change the "status" of the sub-questions.

We can use binary representation for the status of the element usage. For each element, if it is not used yet, its status is 1; once used, become 0. So there will be 2^n status in total, where n is the total number of elements.

In order to increase efficiency, we need memorization of the results for the status visited previously, which is a very common trick to short the running time. Since we have already calculated it, there's no need for re-calculation. For this question, we will use a hashmap for implementation.

Another parameter for each sub-status is the target value, and it will also changes (becomes smaller) as some elements is chosen. So here we will use a vector<unordered_map<int, bool> > structure to store the status information, to memorize both the target value and status information. The index of the vector will be used for the target value.

The two players in this game will always play optimally, so once there is one way that the second player cannot win, the first will win. If for all the possible ways, the second player can always win, then the first player have to lose. At this point, we will use dsf strategy for searching.

Code:

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        int m = maxChoosableInteger, d = desiredTotal;
        if(m>=d) return true;
        if(m*(m+1)<d*2) return false;
        vector<unordered_map<int, bool>> dp(d);
        int t = (1<<m) - 1;
        return canWin(m, d, dp, t);
    }
private:
    bool canWin(int m, int d, vector<unordered_map<int, bool>> &dp, int sta){
        if(dp[d-1].count(sta)) return dp[d-1][sta];
        for(int i=0; i<m; ++i){
            if((1<<i)&sta){// i element is not used.
                if(i+1>=d || !canWin(m, d-i-1, dp, sta^(1<<i))){
                    dp[d-1][sta] = true;
                    return true;
                }
            }
        }
        dp[d-1][sta] = false;//the second player always win.
        return false;
    }
}; 

After finishing this, also noticed that there are some other way for implementation, and here is one example with discussion:

https://discuss.leetcode.com/topic/68896/java-solution-using-hashmap-with-detailed-explanation

"After solving several "Game Playing" questions in leetcode, I find them to be pretty similar. Most of them can be solved using the top-down DP approach, which "brute-forcely" simulates every possible state of the game.
The key part for the top-down dp strategy is that we need to avoid repeatedly solving sub-problems. Instead, we should use some strategy to "remember" the outcome of sub-problems."

"For this question, the key part is: what is the state of the game? Intuitively, to uniquely determine the result of any state, we need to know:

1. The unchosen numbers
2. The remaining desiredTotal to reach

A second thought reveals that 1) and 2) are actually related because we can always get the 2) by deducting the sum of chosen numbers from original desiredTotal.
Then the problem becomes how to describe the state using 1)."
(one of the equivalent ways to understand this is that if we know condition 1 (the unchosen numbers) only, then we can determine the state completely, since that every element can be only used once.)

So only one hashmap is enough to memorize the sub-status for choosing elements.

Code:

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        int m = maxChoosableInteger, d = desiredTotal;
        if(m>=d) return true;
        if(m*(m+1)<d*2) return false;
        unordered_map<int, bool> dp;
        return canWin(m, d, dp, 0);
    }
private:
    bool canWin(int m, int d, unordered_map<int, bool> &dp, int sta){
        if(dp.count(sta)) return dp[sta];
        for(int i=0; i<m; ++i){
            if(((1<<i)&sta)==0){
                if(i+1>=d || !canWin(m, d-i-1, dp, sta|(1<<i))){
                    dp[sta] = true;
                    return true;
                }
            }
        }
        dp[sta] = false;
        return false;
    }
};  

306. Additive Number

https://leetcode.com/problems/additive-number/

Solution:
use DSF strategy. It is kinds of brute force implementation. As long as one is found (or reaching to the end of the string in the DSF search), return true. After all tries, return false. For the overflow, can use string instead of integer for the adding. See code below.

Code:

class Solution {
public:
    bool isAdditiveNumber(string num) {
        int l = num.size();
        if(l<3) return false;
        for(int i=1; i<l-1; ++i){
            for(int j=i+1; j<l; ++j){
                string s1 = num.substr(0, i);
                string s2 = num.substr(i, j-i);
                if(dsf(num, j, s2, add(s1, s2))) return true;
                if(num[i] == '0') break;
            }
            if(num[0] == '0') break;
        }
        return false;
    }
private:
    bool dsf(string num, int ind, string s1, string s2){
            if(num.size()-ind < s2.size()) return false;
            if(num.substr(ind) == s2) return true;
            for(int i=0; i<s2.size(); ++i){
                if(s2[i] != num[ind+i]) return false;
            }
            ind += s2.size();
            return dsf(num, ind, s2, add(s1, s2));
        }
    string add(string s1, string s2){
        if(s1.size()>s2.size()) return add(s2, s1);
        if(s1.empty()) return s2;
        string res;
        int carrier = 0;
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        for(int i=0; i<s1.size(); ++i){
            int t = carrier + (s1[i]-'0') + (s2[i] - '0');
            carrier = t/10;
            t %= 10;
            res.push_back(t+'0');
        }
        for(int i=s1.size(); i<s2.size(); ++i){
            int t = carrier + s2[i] - '0';
            carrier = t/10;
            t %= 10;
            res.push_back(t+'0');
        }
        if(carrier) res.push_back(carrier+'0');
        reverse(res.begin(), res.end());
        return res;
    }
};

488. Zuma Game

https://leetcode.com/problems/zuma-game/

Solution:
will use dsf strategy to find the minimum steps for reaching the end(empty string). If find two same adjacent elements and also have more than one at hand, then match to cancel them; if can only find one element which is different from its left and right neighbors, and there are more than two that kind of elements at hand, then add two to match to cancel. After each canceling, need to consider possible sequential canceling. For example, GGRRGG. When the mid RR was cancelled, then the rest GGGG will cancel automatically.

Code:

class Solution {
public:
    int findMinStep(string board, string hand) {
        int res = INT_MAX;
        vector<int> v(26, 0);
        for(auto a:hand) ++v[a-'A'];
        dsf(board, hand.size(), v, 0, res);
        return res==INT_MAX?-1:res;
    }
private:
    void dsf(string b, int l, vector<int> &v, int count, int &r){
        if(b.size()>=3) b = helper(b);
        if(b.empty()) r = min(r, count);
        else if(l<=0) return;
        else{
            for(int i=0; i<b.size(); ++i){
                if(i<b.size()-1 && b[i]==b[i+1] && v[b[i]-'A']){
                    --v[b[i]-'A'];
                    b.insert(i+b.begin(), b[i]);
                    dsf(b, l-1, v, count+1, r);
                    b.erase(i+b.begin());
                    ++v[b[i]-'A'];
                }
                else{
                    if(v[b[i]-'A'] >= 2){
                        v[b[i]-'A'] -= 2;
                        char t = b[i];
                        b.erase(i+b.begin());//corner case: b may become empty now.
                        dsf(b, l-2, v, count+2, r);
                        b.insert(i+b.begin(), t);
                        v[b[i]-'A'] += 2;
                    }
                }
            }
        }
    }
    string helper(string s){
        bool flag = true;
        while(s.size()>=3 && flag){
            for(int i=0; i<s.size()-2; ++i){
                if(s[i]==s[i+1] && s[i] == s[i+2]){
                    int t = 3;
                    while(i+t<s.size() && s[i] == s[i+t]) ++t;//more than 3. 
                    s.erase(s.begin()+i, s.begin()+i+t);
                    flag = true;
                    break;
                }
                else flag = false;
            }
        }
        return s;
    }
};

211. Add and Search Word - Data structure design

https://leetcode.com/problems/add-and-search-word-data-structure-design/

Solution:
May use the prefix trie data structure. Then need DSF for the word searching. As long as there is one path is right, return true; otherwise, return false.

Code:

class WordDictionary {
public:
    struct TrieNode{
        bool end;
        vector<TrieNode*> children;
        TrieNode(): end(false), children(26, NULL) {}
    };
    
    WordDictionary(){//constructor;
        root = new TrieNode();
    }
    // Adds a word into the data structure.
    void addWord(string word) {
        TrieNode *t = root;
        for(auto a:word){
            if(!t->children[a-'a']) t->children[a-'a'] = new TrieNode();
            t = t->children[a-'a'];
        }
        t->end = true;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return swDSF(word, root, 0);
    }
    
    bool swDSF(string w, TrieNode* r, int i){
        if(i == w.size()) return r->end;
        if(w[i] == '.'){
             for(auto a:r->children){
                if(a && swDSF(w, a, i+1)) return true;
            }
            return false;
        }
        return r->children[w[i]-'a'] && swDSF(w, r->children[w[i]-'a'], i+1);
    }
    
private:
    TrieNode *root;
};
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

139. Word Break

https://leetcode.com/problems/word-break/

Solution:
1) Brute force DSF Recursion. But will cause TLE (not surprisingly);
2) DP. Suppose dp[i] represents the true status (can be separated into words) of substring from 0 to i, then dp[i+1] will be true if both dp[j] and wordDict.find(s.substr(j, i+1-j)) are true for 0<= j <i. Similar dp argument can also applied from right to left, and actually this one can be used to reduce the time complexity for the next question (II) (the details for the implementation will be a little bit different, see below. And also dp[i] now means the substring from i to n can be segmented).

Code:
DSF Recursion:

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        if(s.empty()) return false;
        if(wordDict.find(s) != wordDict.end()) return true;
        for(int i=0; i<s.size(); ++i){
            string t = s.substr(0, i+1);
            if(wordDict.find(t)) != wordDict.end() && wordBreak(s.substr(i+1), wordDict)) return true;
        }
        return false;
    }
};

DP: from left to right

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int l = s.size();
        if(!l) return false;
        vector<bool> dp(l+1, false);
        dp[0] = true;
        for(int i=1; i<=s.size(); ++i){
            for(int j=0; j<i; ++j){
                if(wordDict.find(s.substr(j, i-j)) != wordDict.end() && dp[j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[l];
    }
};

DP: from right to left

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int l = s.size();
        if(!l) return false;
        vector<bool> dp(l+1, false);
        dp[l] = true;
        for(int i=l-1; i>=0; --i){
            for(int j=l; j>i; --j){
                if(wordDict.find(s.substr(i, j-i)) != wordDict.end() && dp[j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
};

140. Word Break II

https://leetcode.com/problems/word-break-ii/

Solution:
May use DSF. In order to reduce the time complexity, we can pre-build a one dimensional array dp[i] to represents that the sub-string from i to n can be segmented into words.

Code:

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        vector<string> res;
        int l = s.size(); 
        if(!l) return res;
        vector<bool> dp(l+1, false);
        dp[l] = true;
        for(int i=l-1; i>=0; --i){
            for(int j=l; j>i; --j){
                if(wordDict.find(s.substr(i, j-i)) != wordDict.end() && dp[j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        wBDSF(s, wordDict, dp, 0, "", res);
        return res;
    }
private:
    void wBDSF(string s, unordered_set<string> &w, vector<bool> &dp, int ind, string t, vector<string> &r){
        if(ind == s.size()) r.push_back(t);
        else{
            for(int i=ind; i<s.size(); ++i){
                string t1 = s.substr(ind, i-ind+1);
                if(w.find(t1) != w.end() && dp[i+1]){
                    wBDSF(s, w, dp, i+1, t.empty()?t+t1:t+" "+t1, r);
                }
            }
        }
    }
}; 

131. Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/

Solution:
Consider to use DSF. The "end condition" or "basic case" is when the search reaches the end of the string. Also need to determine whether all the possible substrings are palindrome or not.

Code:

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        if(!s.size()) return res;
        vector<string> temp;
        vector<vector<bool>> isP(s.size(), vector<bool>(s.size(), false));
        for(int i=s.size()-1; i>=0; --i){//DP for judging palindrome;
            for(int j=i; j<s.size(); ++j){
                if(s[i]==s[j] && (j-i<=2 || isP[i+1][j-1])) isP[i][j] = true;
            }
        }
        pDSF(s, 0, temp, isP, res);
        return res;
    }
private:
    void pDSF(string s, int ind, vector<string> &t, vector<vector<bool>> &isP, vector<vector<string>> &r){
        if(ind == s.size()) r.push_back(t);
        else{
            for(int i=ind; i<s.size(); ++i){
                if(isP[ind][i]){
                    t.push_back(s.substr(ind, i+1-ind));
                    pDSF(s, i+1, t, isP, r);
                    t.pop_back();
                }
            }
        }
    }
};

473. Matchsticks to Square

https://leetcode.com/contest/leetcode-weekly-contest-13/problems/matchsticks-to-square/

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you can save this little girl or not.

Note:

    The length sum of the given matchsticks is in the range of 0 to 10^9.
    The length of the given matchstick array will not exceed 15.

Solution:
some condition needs to be true if the final result is true:
1: the total number of the elements in the array needs to be at least 4;
2: the average needs to be divided by 4 exactly;
3: the largest elements in the array cannot be larger than the average;
4: the most difficult part: those elements has to be packaged exactly and fully into 4 containers with the same size of the average, and each elements can only be used once;

Code:

class Solution {
public:
    bool makesquare(vector<int>& nums) {
        if(nums.size()<4) return false;
        int ave = 0, left = 0, len = 0;
        for(int i=0; i<nums.size(); ++i){
            ave +=nums[i]/4;
            left +=nums[i]%4;
        }
        if(left%4) return false;
        else len = ave + left/4;
        for(auto i:nums){
              if(i>len) return false;
        }
        vector<int> side(4, 0);
        return fitDSF(nums, 0, len, side);
    }
private:
    bool fitDSF(vector<int> &n, int ind, int l, vector<int> &s){
        if(ind == n.size()) return true;
        for(int i=0; i<4; ++i){
            if(i>0&&s[i] == s[i-1]) continue;//if not included, will cause TLE...
            if(s[i] + n[ind] <= l){
                s[i] += n[ind];
                if(fitDSF(n, ind+1, l, s)) return true;
                s[i] -= n[ind];
            }
        }
        return false;
    }
};