单词博弈Java实现(借鉴“miss若尘”博客中写的解题思路)

单词博弈Java实现

，已经通过庞果网的用例测试。

代码如下

import java.util.HashMap;
public class WordGameFinalTest 
{ 
   public static  int who(String word)
    {
        HashMap<String, Integer> hs = new HashMap<String, Integer>();
        return WordGame(word, hs);
    }
    //start 提示：自动阅卷起始唯一标识，请勿删除或增加。 
    public static void main(String args[]) 
    { 
       System.out.println(who("Test"));
    } 
    //end //提示：自动阅卷结束唯一标识，请勿删除或增加。
    
    
    
    //功能函数块
    private static int WordGame(String word, HashMap<String, Integer> has) {
        // TODO Auto-generated method stub
    	
    	//要求是小写，不大于15位的英文字母，word的前提不用判断，
    	//因为题目中没有说需要抛出异常,没有第三种出口，所以不用考虑
    	
    	
    	//不用加入到容器中，是因为此次判断仅需一步
    	//不用再将length为2的word加入容器中。不用再去容器中匹配，而直接判断就可以
        if (word.length() <= 2)
            return 1;

        //去容器中找。递归时会把已经做过测试的字符串加入Map中
        if (has.containsKey(word)) {
            if (has.get(word) == 0)
            {   //System.out.println(word+"0");
                return 0;}
            else{
                //System.out.println(word+"1");
                return 1;
            }
        }

        if (word.length() == 3) {
        	//长度为三的情况。
            if (!(word.charAt(0) < word.charAt(1) || word.charAt(1) < word
                    .charAt(2))) {
            	
                has.put(word, 0);
                return 0;
            }

            else {
                has.put(word, 1);
                return 1;
            }

        }

        //一个一个删，看剩的是不是严格单调递增
        for (int i = 0; i < word.length(); i++) {
            String snew = new String(word.substring(0, i)
                    + word.substring(i + 1));
            if (isOrdered(snew)) {
                has.put(word, 1);
                return 1;
            }
        }

        
        //如果还没有判断出来，就得继续下面代码了
        //下面代码才是递归，这个题的核心
        for (int i = 0; i < word.length(); i++) {
            String snew = new String(word.substring(0, i)
                    + word.substring(i + 1));
            
            //递归，如果WordGame(snew, has)==0 /他输的意思/ 你就赢了
            if (WordGame(snew, has) == 0) {
            	
                has.put(word, 1);
                return 1;
            }
        }

        //如果还没判断出来，表示你输了。
        has.put(word, 0);
        return 0;

    }

    
    //判断s是否是严格单调递增的函数
    public static boolean isOrdered(String s) {

        // if(con.contains(s) ) return true;

        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) >= s.charAt(i + 1)) {
                return false;
            }
        }

        return true;
    }
}