Leetcode: 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. For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+". Follow up: Derive your algorithm's runtime complexity.
The idea is try to replace every "++"
in the current string s
to "--"
and see if the opponent has the chance to win or not, if the opponent is guaranteed to lose, great, we win!
For the time complexity, here is what I thought, let's say the length of the input string s
is n
, there are at most n - 1
ways to replace "++"
to "--"
(imagine s
is all "+++..."
), once we replace one "++"
, there are at most (n - 2) - 1
ways to do the replacement, it's a little bit like solving the N-Queens problem, the time complexity is (n - 1) x (n - 3) x (n - 5) x ...
, so it'sO(n!!)
, double factorial.
1 public class Solution { 2 public boolean canWin(String s) { 3 if (s==null || s.length()<=1) return false; 4 for (int i=0; i<s.length()-1; i++) { 5 if (s.charAt(i)=='+' && s.charAt(i+1)=='+' && !canWin(s.substring(0,i) + "--" + s.substring(i+2))) 6 return true; 7 } 8 return false; 9 } 10 }
Better Solution: (205ms -> 19ms)
but the time complexity of the backtracking method is high. During the process of searching, we could encounter duplicate computation as the following simple case.
One search path:
Input s = "++++++++"
Player 0: "--++++++"
Player 1: "----++++"
Player 0: "----+--+"
Player0 can win for the input string as "----++++".
Another search path:
Player 0: "++--++++"
Player 1: "----++++"
Player 0: "----+--+"
(Duplicate computation happens. We have already known anyone can win for the
input string as "----++++".)
Use a HashMap to avoid duplicate computation
Key : InputString.
Value: can win or not.
1 public boolean canWin(String s) { 2 if (s == null || s.length() < 2) { 3 return false; 4 } 5 HashMap<String, Boolean> winMap = new HashMap<String, Boolean>(); 6 return helper(s, winMap); 7 } 8 9 public boolean helper(String s, HashMap<String, Boolean> winMap) { 10 if (winMap.containsKey(s)) { 11 return winMap.get(s); 12 } 13 for (int i = 0; i < s.length() - 1; i++) { 14 if (s.startsWith("++", i)) { 15 String t = s.substring(0, i) + "--" + s.substring(i+2); 16 if (!helper(t, winMap)) { 17 winMap.put(s, true); 18 return true; 19 } 20 } 21 } 22 winMap.put(s, false); 23 return false; 24 }
Reference: https://leetcode.com/discuss/64291/share-my-java-backtracking-solution
https://leetcode.com/discuss/64486/backtracking-solution-time-optimization-through-205ms-19ms
相关文章
- Java实现 LeetCode 803 打砖块 (DFS)
- Java实现 LeetCode 793 阶乘函数后K个零 (分析)
- Java实现 LeetCode 680 验证回文字符串 Ⅱ(暴力)
- Java实现 LeetCode 552 学生出勤记录 II(数学转换?还是动态规划?)
- Java实现 LeetCode 454 四数相加 II
- Java实现 LeetCode 407 接雨水 II(二)
- Java实现 LeetCode 350 两个数组的交集 II(二)
- Java实现 LeetCode 295 数据流的中位数
- Java实现 LeetCode 200 岛屿数量
- Java实现 LeetCode 154 寻找旋转排序数组中的最小值 II(二)
- Java实现 LeetCode 137 只出现一次的数字 II(二)
- Java实现 LeetCode 126 单词接龙 II
- Java实现 LeetCode 31下一个排列
- Java实现 LeetCode 240 搜索二维矩阵 II
- (LeetCode 49)Anagrams
- LeetCode:151_Reverse Words in a String | 字符串中单词的逆反 | Medium
- [LeetCode] Repeated DNA Sequences
- LeetCode(119):杨辉三角 II
- LeetCode(59):螺旋矩阵 II
- LeetCode-667. 优美的排列 II【数组,数学】
- Leetcode学习计划之动态规划入门day15(62,63)
- leetcode_Jump Game II
- [LeetCode]Best Time to Buy and Sell Stock II
- 【Leetcode刷题Python】105. 从前序与中序遍历序列构造二叉树
- 【Leetcode刷题Python】50. Pow(x, n)
- LeetCode 350. 两个数组的交集 II