The Wording Game — LeetCode 2868 Python Solution

The problem

Alice and Bob each have a lexicographically sorted array of strings named a and b respectively. They are playing a wording game with the following rules: On each turn, the current player should play a word from their list such that the new word is closely greater than the last played word; then it's the other player's turn.

Example

Input

a = ["avokado","dabar"], b = ["brazil"]

Output

false

Explanation

Alice must start the game by playing the word "avokado" since it's her smallest word, then Bob plays his only word, "brazil", which he can play because its first letter, 'b', is the letter after Alice's word's first letter, 'a'.

Python solution

class Solution:
    def canAliceWin(self, a: List[str], b: List[str]) -> bool:
        i, j, k = 1, 0, 1
        w = a[0]
        while 1:
            if k:
                if j == len(b):
                    return True
                if (b[j][0] == w[0] and b[j] > w) or ord(b[j][0]) - ord(w[0]) == 1:
                    w = b[j]
                    k ^= 1
                j += 1
            else:
                if i == len(a):
                    return False
                if (a[i][0] == w[0] and a[i] > w) or ord(a[i][0]) - ord(w[0]) == 1:
                    w = a[i]
                    k ^= 1
                i += 1

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 2868. The Wording Game is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems