难度: Hard
Submission
运行时间: 96 ms
内存: 42.2 MB
class Solution:
def canAliceWin(self, a: List[str], b: List[str]) -> bool:
left = [''] * 27
right = [''] * 27
for s in a:
left[ord(s[0])-ord('a')] = s
for s in b:
right[ord(s[0])-ord('a')] = s
def pick(last,arr):
i = ord(last[0])-ord('a')
if i < 25:
if arr[i+1]:
return arr[i+1]
if arr[i] and arr[i] > last:
return arr[i]
return last
# 当前能否获胜
@cache
def dfs(last,flag):
i = ord(last[0])-ord('a')
# a选
if flag:
if left[i] and left[i] > last:
if not dfs(left[i],not flag):
return True
if left[i+1]:
if not dfs(left[i+1],not flag):
return True
return False
# b选
else:
if right[i] and right[i] > last:
if not dfs(right[i],not flag):
return True
if right[i+1]:
if not dfs(right[i+1],not flag):
return True
return False
return not dfs(a[0],False)
Explain
这个题解的基本思路是使用深度优先搜索（DFS）来模拟两个玩家（Alice 和 Bob）轮流从两个不同的单词列表中选择单词的游戏。玩家必须选择的单词需要字母顺序大于上一个选择的单词，并且以相邻的字母开头。解题关键是利用缓存（通过@cache装饰器）来避免重复计算相同状态下的结果，提高效率。通过递归调用`dfs`函数来判断当前玩家是否有必胜策略。如果当前玩家能选择一个单词，使得对方在下一轮没有必胜策略，则当前玩家获胜。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def canAliceWin(self, a: List[str], b: List[str]) -> bool:
left = [''] * 27
right = [''] * 27
for s in a:
left[ord(s[0])-ord('a')] = s
for s in b:
right[ord(s[0])-ord('a')] = s
@cache
def dfs(last, flag):
i = ord(last[0])-ord('a')
if flag: # Alice's turn
if left[i] and left[i] > last:
if not dfs(left[i], not flag):
return True
if left[i+1]:
if not dfs(left[i+1], not flag):
return True
return False
else: # Bob's turn
if right[i] and right[i] > last:
if not dfs(right[i], not flag):
return True
if right[i+1]:
if not dfs(right[i+1], not flag):
return True
return False
return not dfs(a[0], False)
Explore
在题解中，`字母顺序大于上一个选择的单词`指的是比较两个单词的整个字符串的字典序。这意味着如果在字典中，一个单词（例如'bcd'）出现在另一个单词（例如'abc'）之后，则第一个单词在字典序上大于第二个单词。题解中的比较操作`left[i] > last`或`right[i] > last`就是执行这样的字典序比较，确保所选的单词在字典序上严格大于上一个选中的单词。
在`dfs`函数中，`not dfs(left[i], not flag)`返回True表示如果当前玩家选择单词`left[i]`后，对手在接下来的回合中没有必胜策略。这是因为`dfs`函数设计为判断当前玩家是否会输掉游戏（即对手有必胜策略）。因此，如果对手的`dfs`调用返回False（表示对手无法必胜），那么`not dfs(...)`就会返回True，显示当前玩家通过选择这个单词能够迫使对手进入一个必败的状态。这正是体现当前玩家拥有必胜策略的关键逻辑。
题解中使用的缓存是通过Python的`@cache`装饰器实现的，它是一种优化技术，用于存储已解决的子问题的结果。在递归过程中，某些状态可能会被重复计算多次，特别是在深度优先搜索中，这会导致效率低下。通过存储已计算过的函数结果，当相同的输入再次出现时，可以直接返回存储的结果，避免重复计算。在这个问题中，缓存存储了每个`(last, flag)`状态的结果，防止在探索不同路径时对相同的游戏状态进行重复的胜负判定。
题解通过将首字母转换为Ascii码偏移量来初始化`left`和`right`数组，这样做可以快速定位到以特定字母开头的单词。这种方法的优点在于它提供了一种快速的索引方式，允许算法直接访问以任何特定字母开头的最大单词，而无需遍历整个单词列表。这种基于首字母索引的方式减少了查找时间，使得算法在处理大量单词时更加高效。此外，这种方法在处理字母开头的排序和比较时也更为直观和方便。