Super easy 10ms 98.5% Solution - BackTrack w/ Memorization


  • 1
    O

    In addition to the best-voted backtracking solution, I added a hashmap to memorize repeating solution. Below is my code. I also demonstrate to you how memorization saves repeating work by printing result with "==>".

        public boolean canWin(String s) {
            HashMap<String, Boolean> h = new HashMap();
            return canWin(s.toCharArray(), h);
        }
        
        private boolean canWin(char[] c, HashMap<String, Boolean> h) {
            for (int i = 1; i < c.length; i++)
                if (c[i] == '+' && c[i - 1] == '+') {
                    c[i] = '-'; c[i - 1] = '-';
                    
                    boolean t;
                    String key = String.valueOf(c);
                    if (!h.containsKey(key)) {
                        t = canWin(c, h);
                        h.put(key, t);      //System.out.println(key + " --> " + t);
                    } else {
                        t = h.get(key);     //System.out.println(key + " ==> " + t);
                    }   // can not directly use if (t) return true here, cuz you need to restore
                    
                    c[i] = '+'; c[i - 1] = '+';
                    if (!t) return true;
                }
            return false;
        }
    
    Example: "++++++++++"
    
    ---------- --> false
    --------++ --> true
    ------+--+ --> false
    ------++++ --> true
    ----+----+ --> false
    ----+--+++ --> true
    --------++ ==> true
    ---------- ==> false
    ----++---- --> true
    ----++--++ --> false
    ----++++++ --> true
    --+------+ --> false
    --+----+++ --> true
    --+--+---- --> false
    --+--+--++ --> true
    --+------+ ==> false
    --+--++--+ --> true
    --+----+-- --> false
    --+--+++-- --> true
    --+--+++++ --> false
    --++++++++ --> true
    +--------+ --> false
    +------+++ --> true
    +----+---- --> false
    +----+--++ --> true
    +--------+ ==> false
    +----++--+ --> true
    +------+-- --> false
    +----+++-- --> true
    +----+++++ --> false
    +--+++++++ --> true
    ----++++++ ==> true
    ------++++ ==> true
    --------++ ==> true
    ---------- ==> false
    ++-------- --> true
    ++------++ --> false
    ++----++++ --> true
    ----+--+++ ==> true
    ----+----+ ==> false
    ++--+----+ --> true
    ----+--+-- --> false
    ++--+--+-- --> true
    ++--+--+++ --> false
    ++--++++++ --> true
    --+--+++++ ==> false
    +++--+++++ --> true
    ------++++ ==> true
    --------++ ==> true
    ---------- ==> false
    --++------ --> true
    --++----++ --> false
    --++--++++ --> true
    +--+------ --> false
    +--+----++ --> true
    +--+--+--+ --> false
    +--+--++++ --> true
    ++----++++ ==> true
    --++----++ ==> false
    ++++----++ --> true
    ------+--+ ==> false
    --++--+--+ --> true
    +--+--+--+ ==> false
    ++++--+--+ --> true
    ---------- ==> false
    ------++-- --> true
    --++------ ==> true
    --++--++-- --> false
    ++++--++-- --> true
    ++++--++++ --> false

Log in to reply
 

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