# 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& a, vector& 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> words(2, vector(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