| comments | difficulty | edit_url | tags | |||||
|---|---|---|---|---|---|---|---|---|
true |
困难 |
|
Alice 和 Bob 分别拥有一个 按字典序排序 的字符串数组，分别命名为 a 和 b。
他们正在玩一个单词游戏，遵循以下规则：
- 每一轮，当前玩家应该从他的列表中选择一个单词，并且选择的单词比上一个单词 紧邻大；然后轮到另一名玩家。
- 如果一名玩家在自己的回合中无法选择单词，则输掉比赛。
Alice 通过选择在 字典序最小 的单词开始游戏。
给定 a 和 b，已知两名玩家都按最佳策略玩游戏，如果 Alice 可以获胜，则返回 true ，否则返回 false。
如果满足以下条件，则称一个单词 w 比另一个单词 z 紧邻大：
w在 字典序上大于z。- 如果
w1是w的第一个字母，z1是z的第一个字母，那么w1应该 等于z1或者是字母表中z1后面相邻 的字母。 - 例如，单词
"care"比"book"和"car"紧邻大，但不比"ant"或"cook"紧邻大。
如果在 s 和 t 不同的第一个位置处，字符串 s 的字母比字符串 t 的字母在字母表中的顺序更靠后，则称为字符串 s 在 字典序上大于 字符串 t。如果前 min(s.length, t.length) 个字符没有区别，那么较长的字符串是在字典序上较大的那一个。
示例 1：
输入: a = ["avokado","dabar"], b = ["brazil"] 输出: false 解释: Alice 必须从单词 "avokado" 来开始游戏，因为这是她最小的单词，然后 Bob 使用他唯一的单词 "brazil"，他可以使用它因为它的第一个字母 'b' 在 Alice 的单词的第一个字母 'a' 之后。 Alice 无法出牌，因为剩下的唯一单词的第一个字母既不等于 'b' 也不是 'b' 之后的字母 'c'。 所以，Alice 输了，游戏结束。
示例 2：
输入: a = ["ananas","atlas","banana"], b = ["albatros","cikla","nogomet"] 输出: true 解释: Alice 必须从单词 "ananas" 来开始游戏。 Bob 无法出牌，因为他唯一拥有的以字母 'a' 或 'b' 开头的单词是 "albatros"，而它比 Alice 的单词小。 所以，Alice 获胜，游戏结束。
示例 3：
输入: a = ["hrvatska","zastava"], b = ["bijeli","galeb"] 输出: true 解释: Alice 必须从单词 "hrvatska" 来开始游戏。 Bob 无法出牌，因为他的两个单词的第一个字母都比 Alice 的单词的第一个字母 'h' 小。 所以，Alice 获胜，游戏结束。
约束条件：
1 <= a.length, b.length <= 105a[i]和b[i]仅包含小写英文字母。a和b按 字典序排序。a和b中所有的单词都是 不同的。a和b中所有单词的长度之和不超过106。
我们记当前轮到
我们不断地进行如下操作：
如果
如果
时间复杂度
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 += 1class 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;
}
}
}