leetcode解题: Flip Game (293)

发表于 | 分类于

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 compute all possible states of the string after one valid move.

For example, given s = “++++”, after one move, it may become one of the following states:

[
“–++”,
“+–+”,
“++–”
]
If there is no valid move, return an empty list [].

解法1：DP with O(N) time, N = number of characters

按顺序一个个查看是否连续的两个字符是’+’， 如果是则换，如果不是继续
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<string> generatePossibleNextMoves(string s) {
        vector<string> result;
        if (s.length() == 0) {
            return result;
        }
        for (int i = 0; i < s.length() - 1; i++) {
            if (s[i] == '+' && s[i+1] == '+') {
                string temp = s.substr(0); // or just string temp = s;
                temp[i] = '-';
                temp[i + 1] = '-';
                result.push_back(temp);
            }
        }
        return result;
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public List<String> generatePossibleNextMoves(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return result;
        }
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '+' && s.charAt(i + 1) == '+') {
                StringBuffer temp = new StringBuffer(s);
                temp.setCharAt(i, '-');
                temp.setCharAt(i + 1, '-');
                result.add(temp.toString());
            }
        }
        return result;
    }
}