Skip to content

2868. The Wording Game

  • Time: $O(n)$
  • Space: $O(\Sigma |\texttt{a[i]}| + \Sigma |\texttt{b[i]}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
 public:
  bool canAliceWin(vector<string>& a, vector<string>& b) {
    // words[0][i] := the biggest word starting with ('a' + i) for Alice
    // words[1][i] := the biggest word starting with ('a' + i) for Bob
    vector<vector<string>> words(2, vector<string>(26));

    // For each letter, only the biggest word is useful.
    for (const string& word : a)
      words[0][word[0] - 'a'] = word;

    for (const string& word : b)
      words[1][word[0] - 'a'] = word;

    // Find Alice's smallest word.
    int i = 0;
    while (words[0][i].empty())
      ++i;

    // Iterate each letter until we find a winner.
    // Start with Alice's turn (0), so it's Bob's turn (1) now.
    for (int turn = 1; true; turn = turn ^ 1)
      // If the current player has a word that having the letter that is greater
      // than the opponent's word, choose it.
      if (!words[turn][i].empty() && words[turn][i] > words[turn ^ 1][i]) {
        // Choose the current words[turn][i].
      } else if (!words[turn][i + 1].empty()) {
        // Choose the next words[turn][i + 1].
        ++i;
      } else {
        // Game over. If it's Bob's turn, Alice wins, and vice versa.
        return turn == 1;
      }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
  public boolean canAliceWin(String[] a, String[] b) {
    // words[0][i] := the biggest word starting with ('a' + i) for Alice
    // words[1][i] := the biggest word starting with ('a' + i) for Bob
    String[][] words = new String[2][26];

    // For each letter, only the biggest word is useful.
    for (final String word : a)
      words[0][word.charAt(0) - 'a'] = word;

    for (final String word : b)
      words[1][word.charAt(0) - 'a'] = word;

    // Find Alice's smallest word.
    int i = 0;
    while (words[0][i] == null)
      ++i;

    // Iterate each letter until we find a winner.
    // Start with Alice's turn (0), so it's Bob's turn (1) now.
    for (int turn = 1; true; turn = turn ^ 1)
      // If the current player has a word that having the letter that is greater
      // than the opponent's word, choose it.
      if (words[turn][i] != null && words[turn][i].compareTo(words[1 - turn][i]) > 0) {
        // Choose the current words[turn][i].
      } else if (words[turn][i + 1] != null) {
        // Choose the next words[turn][i + 1].
        ++i;
      } else {
        // Game over. If it's Bob's turn, Alice wins, and vice versa.
        return turn == 1;
      }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
  def canAliceWin(self, a: List[str], b: List[str]) -> bool:
    # words[0][i] := the biggest word starting with ('a' + i) for Alice
    # words[1][i] := the biggest word starting with ('a' + i) for Bob
    words = [[''] * 26 for _ in range(2)]

    # For each letter, only the biggest word is useful.
    for word in a:
      words[0][ord(word[0]) - ord('a')] = word

    for word in b:
      words[1][ord(word[0]) - ord('a')] = word

    # Find Alice's smallest word.
    i = 0
    while not words[0][i]:
      i += 1

    # 0 := Alice, 1 := Bob
    # Start with Alice, so it's Bob's turn now.
    turn = 1

    # Iterate each letter until we find a winner.
    while True:
      # If the current player has a word that having the letter that is greater
      # than the opponent's word, choose it.
      if words[turn][i] and words[turn][i] > words[1 - turn][i]:
        # Choose the current words[turn][i].
        pass
      elif words[turn][i + 1]:
        # Choose the next words[turn][i + 1].
        i += 1
      else:
        # Game over. If it's Bob's turn, Alice wins, and vice versa.
        return turn == 1
      turn = 1 - turn