Short Java & Ruby


  • 6

    You win if and only if you can make some move so that the resulting state can't be won. One thing I do differently from everyone else so far is that I replace "++" with "-" instead of "--".


    Ruby

    def can_win(s)
      (0..s.size).any? { |i| s[i,2] == "++" && !can_win(s[0, i] + "-" + s[i+2..-1]) }
    end
    

    Java

    I let the library do the searching for "++", which I find nicer and apparently it's faster as well (see below).

    public boolean canWin(String s) {
        for (int i=-1; (i = s.indexOf("++", i+1)) >= 0; )
            if (!canWin(s.substring(0, i) + "-" + s.substring(i+2)))
                return true;
        return false;
    }
    

    Both the library-searching and the "-"-replacement seem to speed it up significantly, here are results of submitting different similar solutions five times each:

    Average 153 ms: Mine with "-" (150, 156, 152, 149 and 156)
    Average 169 ms: Mine with "--" (184, 169, 156, 162 and 174)
    Average 209 ms: easonhu's (214, 204, 207, 207 and 213)
    Average 221 ms: jeantimex's (168, 196, 202, 194 and 345) (without the 345 the average is 190 ms)


  • 0

    Oh, I understand the Java version now. Really cool and simple, both the idea and the code. Almost the simplest solution that I have seen :-)

    I try to rewrite it in C++ :-)

    class Solution {
    public:
        bool canWin(string s) {
            for (int i = -1; (i = s.find("++", i + 1)) >= 0; )
                if (!canWin(s.substr(0, i) + '-' + s.substr(i+2)))
                    return true;
            return false;
        }
    };

  • 4
    J

    Stefan, you can really speed it up by avoiding building string objects. The usage of chars[] for the backtracking can go down to 27ms. Try this one:

    public boolean canWin(String s) {
    	if (s == null) return false;  	
    	return canWin(s.toCharArray());
    }
    private boolean canWin(char[] chars) {
       for (int i = 0; i < chars.length - 1; i++) {
        	if (chars[i] == '+' && chars[i+1] == '+') {
        		chars[i] = chars[i+1] = '-';
        		boolean win = !canWin(chars);
        		chars[i] = chars[i+1] = '+'; //backtrack.
        		if (win)
        			return true;
        	}
        }
        return false;
    }

  • 0

    But then it doesn't look as nice :-D. Good point, though, especially since I started with the speed-testing.


  • 0
    K

    Is the complexity of this solution exponential?


  • 0

    @khing I don't think so. But it can be made exponential, as I did for example here.


Log in to reply
 

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