memoization c++ solution


  • 1
    I
    class Solution {
    public:
    	bool removeCon(std::string& str) {
    		int con = 1;
    		for (size_t i = 1; i < str.size(); i++) {
    			if (str[i] == str[i - 1]) {
    				con++;
    			} else {
    				if (con >= 3) {
    					str.erase(i - con, con);
    					return true;
    				}
    				con = 1;
    			}
    		}
    
    		if (con >= 3) {
    			str.erase(str.size() - con, con);
    			return true;
    		}
    
    		return false;
    	}
    
        int solve(string board, string hand) {
    		while (removeCon(board));
    
    		if (board.empty()) {
    			return 0;
    		}
    
    		if (hand.empty() || board.size() + hand.size() < 3) {
    			return -1;
    		}
    
    		auto it = f.find(std::make_pair(board, hand));
    		if (it != f.end()) {
    			return it->second;
    		}
    
    		int best = -1;
    		for (size_t i = 0; i < hand.size(); i++) {
    			for (size_t j = 0; j < board.size(); j++) {
    				if (board[j] == hand[i]) {
    					std::string new_board = board;
    					std::string new_hand = hand;
    
    					new_board.insert(new_board.begin() + j, hand[i]);
    					new_hand.erase(i, 1);
    					int ret = solve(new_board, new_hand);
    					if (ret > -1) {
    						if (best == -1) {
    							best = ret + 1;
    						} else {
    							best = std::min(best, ret + 1);
    						}
    					}
    				}
    			}
    		}
    
    		f[std::make_pair(board, hand)] = best;
    		return best;
        }
    
    	int findMinStep(string board, string hand) {
    		f.clear();
    		std::sort(hand.begin(), hand.end());
    		return solve(board, hand);
    	}
    
    	std::map<std::pair<std::string, std::string>, int> f;
    };
    

  • 1

    Nice clean recursive solution. I have posted a similar recursive solution to yours. I think you can make several improvements to minimize the number of recursive calls to solve:

    1. If a letter c in board has total count < 3 in board and hand combined, obviously, we cannot empty the board. This is more general than board.size() + hand.size() < 3.
    2. If a letter c in hand does not appear in board, such letter is useless and should be abandoned.
    3. No need to try index j in loop for (size_t j = 0; j < board.size(); j++) if it results to a new_board which has been tried before.
    4. No need to try index i in loop for (size_t i = 0; i < hand.size(); i++) if letter hand[i] has been tried before.
        int findMinStep(string b, string h) {
          // pre-process
          string a; int L, r = 0;
          for (char c:b) // shrink b to remove consecutive identical letters
            if (c-r) if ((L=a.size()) < 2 || c-a[L-1] || c-a[L-2]) a += c, r = 0;
                     else r = c, a.pop_back(), a.pop_back();
          sort(h.begin(), h.end()); // sort hand for memorization
          
          // memorization
          if (m.count(b=a) && m[b].count(h)) return m[b][h];
            
          // base cases
          if (b.empty()) return 0; else if (h.empty()) return -1;
        
          // edge cases
          for (char c:b) if (count(a.begin(),(a=b+h).end(),c) < 3) return m[b][h] = -1; 
          
          // recursion
          for (int i = 0, res = INT_MAX; i <= h.size(); ++i) {
            if (i==h.size()) return m[b][h] = res<INT_MAX? res : -1;
            if (i && h[i]==h[i-1] || b.find(h[i])==string::npos) continue;
            for (int j = 0, step; j < b.size(); ++j) {
              if (b[j]-h[i] || (j && b[j]==b[j-1])) continue;
              string bb(b); bb.insert(bb.begin() + j, h[i]); // insert h[i] to board
              string hh(h); hh.erase(hh.begin() + hh.find(h[i])); // remove h[i] from hand
              if (step = findMinStep(bb, hh)+1) res = min(res, step);
            }
          }
        }
        
        // m[b][h] = min steps for borad=b & hand=h
        unordered_map<string, unordered_map<string, int>> m;
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.