Very Simple Java DP solution in 36ms with memoization


  • 0
    A
    Map<String,Boolean> MEMO = new HashMap<>();
    public List<String> generatePossibleNextMoves(String s) {
        List<String> res = new ArrayList<>();
        StringBuilder sb ;
        if (s == null || s.length() < 2) return res;
        for (int i = 0; i < s.length()- 1; i++) {
            if (s.substring(i,i + 2).equals("++")) {
                sb = new StringBuilder();
                sb.append(s.substring(0,i));
                sb.append("--");
                sb.append(s.substring(i + 2,s.length()));
                res.add(sb.toString());
            }
        }
        return res;
    }
    public boolean canWin(String s) {
        List<String> pMoves = generatePossibleNextMoves(s);
        if (pMoves.size() == 0) return false;
        if (pMoves.size() == 1) return true;
        for (int i = 0; i < pMoves.size(); i++) {
            boolean res;
            if (MEMO.containsKey(pMoves.get(i))){
                res = MEMO.get(pMoves.get(i));
            }
            else {
                res = canWin(pMoves.get(i));
                MEMO.put(pMoves.get(i),res);
            }
            if (res == false) return true;
        }
        return false;
    }

Log in to reply
 

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