4
假設你正在和你的朋友玩下面的翻轉游戲：給定一個只包含這兩個字符的字符串：+和-，你和你的朋友輪流翻轉兩個連續的"++"到"--"。遊戲結束時，一個人不能再行動，因此另一個人將成爲贏家。如何分析時間複雜性？
寫一個函數來確定起始玩家是否可以保證勝利。
例如，給出s = "++++"，返回true。首發球員可以通過翻轉中間"++"來保證贏得成爲"+--+"。
這裏是我的代碼：
public boolean canWin(String s) {
if(s==null || s.length()<2) return false;
char[] arr=s.toCharArray();
return canWinHelper(arr);
}
public boolean canWinHelper(char[] arr){
for(int i=0; i<arr.length-1; i++){
if(arr[i]=='+' && arr[i+1]=='+'){
arr[i]='-';
arr[i+1]='-';
boolean win=!canWinHelper(arr);
arr[i]='+';
arr[i+1]='+';
if(win) return true;
}
}
return false;
}
它的工作原理，但我不知道這裏怎麼計算時間複雜性，因爲該功能將保持自稱，直到返回一個錯誤。任何人都有一些想法嗎？
另外在搜索期間，我們會遇到重複計算，所以我想我可以使用散列圖來避免這些重複。鍵：字符串，值：布爾值。使用一個HashMap
我更新的代碼：
public boolean canWin(String s){
if(s==null || s.length()<2) return false;
HashMap<String,Boolean> map=new HashMap<String,Boolean>();
return helper(s,map);
}
public boolean helper(String s, HashMap<String,Boolean> map){
if(map.containsKey(s)) return map.get(s);
for(int i=0; i<s.length()-1; i++){
if(s.charAt(i)=='+' && s.charAt(i+1)=='+'){
String fliped=s.substring(0,i)+"--"+s.substring(i+2);
if(!helper(fliped,map)){
map.put(s,true);
return true;
}
}
}
map.put(s,false);
return false;
}
不過，我想知道如何在這裏分析的時間和空間複雜度？
對於散列版本，這是怎麼來的2 ^（n/2）？ –