返回介绍

solution / 2800-2899 / 2868.The Wording Game / README_EN

发布于 2024-06-17 01:02:59 字数 9437 浏览 0 评论 0 收藏 0

2868. The Wording Game

中文文档

Description

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.
  • If a player can't play a word on their turn, they lose.

Alice starts the game by playing her lexicographically smallest word.

Given a and b, return true _if Alice can win knowing that both players play their best, and_ false _otherwise._

A word w is closely greater than a word z if the following conditions are met:

  • w is lexicographically greater than z.
  • If w1 is the first letter of w and z1 is the first letter of z, w1 should either be equal to z1 or be the letter after z1 in the alphabet.
  • For example, the word "care" is closely greater than "book" and "car", but is not closely greater than "ant" or "cook".

A string s is lexicographically greater than a string t if in the first position where s and t differ, string s has a letter that appears later in the alphabet than the corresponding letter in t. If the first min(s.length, t.length) characters do not differ, then the longer string is the lexicographically greater one.

 

Example 1:

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'.
Alice can't play a word since the first letter of the only word left is not equal to 'b' or the letter after 'b', 'c'.
So, Alice loses, and the game ends.

Example 2:

Input: a = ["ananas","atlas","banana"], b = ["albatros","cikla","nogomet"]
Output: true
Explanation: Alice must start the game by playing the word "ananas".
Bob can't play a word since the only word he has that starts with the letter 'a' or 'b' is "albatros", which is smaller than Alice's word.
So Alice wins, and the game ends.

Example 3:

Input: a = ["hrvatska","zastava"], b = ["bijeli","galeb"]
Output: true
Explanation: Alice must start the game by playing the word "hrvatska".
Bob can't play a word since the first letter of both of his words are smaller than the first letter of Alice's word, 'h'.
So Alice wins, and the game ends.

 

Constraints:

  • 1 <= a.length, b.length <= 105
  • a[i] and b[i] consist only of lowercase English letters.
  • a and b are lexicographically sorted.
  • All the words in a and b combined are distinct.
  • The sum of the lengths of all the words in a and b combined does not exceed 106.

Solutions

Solution 1: Simulation

We use $k$ to record whose turn it is, where $k=0$ means it is Alice's turn, and $k=1$ means it is Bob's turn. We use $i$ to record Alice's index, $j$ to record Bob's index, and $w$ to record the current word. Initially, we set $i=1$, $j=0$, and $w=a[0]$.

We perform the following steps repeatedly:

If $k=1$, we check if $j$ is equal to the length of $b$. If it is, then Alice wins and we return $true$. Otherwise, we check if the first letter of $b[j]$ is equal to the first letter of $w$. If it is, we check if $b[j]$ is greater than $w$, or if the first letter of $b[j]$ is one greater than the first letter of $w$. If either of these conditions is true, then Bob can play the $j$-th word. We set $w=b[j]$ and toggle $k$. Otherwise, Bob cannot play the $j$-th word, so we increment $j$.

If $k=0$, we check if $i$ is equal to the length of $a$. If it is, then Bob wins and we return $false$. Otherwise, we check if the first letter of $a[i]$ is equal to the first letter of $w$. If it is, we check if $a[i]$ is greater than $w$, or if the first letter of $a[i]$ is one greater than the first letter of $w$. If either of these conditions is true, then Alice can play the $i$-th word. We set $w=a[i]$ and toggle $k$. Otherwise, Alice cannot play the $i$-th word, so we increment $i$.

The time complexity is $O(m+n)$, where $m$ and $n$ are the lengths of arrays $a$ and $b$, respectively. We only need to traverse the arrays once. The space complexity is $O(1)$.

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
class Solution {
  public boolean canAliceWin(String[] a, String[] b) {
    int i = 1, j = 0;
    boolean k = true;
    String w = a[0];
    while (true) {
      if (k) {
        if (j == b.length) {
          return true;
        }
        if ((b[j].charAt(0) == w.charAt(0) && w.compareTo(b[j]) < 0)
          || b[j].charAt(0) - w.charAt(0) == 1) {
          w = b[j];
          k = !k;
        }
        ++j;
      } else {
        if (i == a.length) {
          return false;
        }
        if ((a[i].charAt(0) == w.charAt(0) && w.compareTo(a[i]) < 0)
          || a[i].charAt(0) - w.charAt(0) == 1) {
          w = a[i];
          k = !k;
        }
        ++i;
      }
    }
  }
}
class Solution {
public:
  bool canAliceWin(vector<string>& a, vector<string>& b) {
    int i = 1, j = 0, k = 1;
    string w = a[0];
    while (1) {
      if (k) {
        if (j == b.size()) {
          return true;
        }
        if ((b[j][0] == w[0] && w < b[j]) || b[j][0] - w[0] == 1) {
          w = b[j];
          k ^= 1;
        }
        ++j;
      } else {
        if (i == a.size()) {
          return false;
        }
        if ((a[i][0] == w[0] && w < a[i]) || a[i][0] - w[0] == 1) {
          w = a[i];
          k ^= 1;
        }
        ++i;
      }
    }
  }
};
func canAliceWin(a []string, b []string) bool {
  i, j, k := 1, 0, 1
  w := a[0]
  for {
    if k&1 == 1 {
      if j == len(b) {
        return true
      }
      if (b[j][0] == w[0] && w < b[j]) || b[j][0]-w[0] == 1 {
        w = b[j]
        k ^= 1
      }
      j++
    } else {
      if i == len(a) {
        return false
      }
      if (a[i][0] == w[0] && w < a[i]) || a[i][0]-w[0] == 1 {
        w = a[i]
        k ^= 1
      }
      i++
    }
  }
}
function canAliceWin(a: string[], b: string[]): boolean {
  let [i, j, k] = [1, 0, 1];
  let w = a[0];
  while (1) {
    if (k) {
      if (j === b.length) {
        return true;
      }
      if ((b[j][0] === w[0] && w < b[j]) || b[j].charCodeAt(0) - w.charCodeAt(0) === 1) {
        w = b[j];
        k ^= 1;
      }
      ++j;
    } else {
      if (i === a.length) {
        return false;
      }
      if ((a[i][0] === w[0] && w < a[i]) || a[i].charCodeAt(0) - w.charCodeAt(0) === 1) {
        w = a[i];
        k ^= 1;
      }
      ++i;
    }
  }
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文