给定一个元组列表，检查是否可以构造一个元组中第二个值没有连续重复的单词

Question

假设我有一个元组列表，如下所示：

list_of_tuples = [('A', 'R'), ('B', 'R'), ('C', 'G'), ('D', 'G'), ('E', 'B'), ('D', 'B'), ('R', 'B'), ('F', 'R'), ('V', 'R'), ('A', 'G')]

每个元组中的第二个值总是R、B或G。我想创建一个函数validate，它检查是否可以使用每个元组第一个位置的字母构造某个单词，但前提是该元组的节位置的字母没有重复

例如，可以构造单词：

由于每个元组中的第二个值对应于不连续重复任何字母的RGB，因此ACE具有(A, R)、(C, G)和(E, B)

ACED与(A, R), (C, G), (E, B), and ('D', 'B')不可能，因为这将对应于RGBB，其中有一个连续的B

请注意，有时同一个字母的第二个位置可能有不同的字母，例如：

('A', 'R') and ('A', 'G')。如果选择第一个元组而不是第二个元组，则只能拼写ACE，否则G会重复

还要注意，像GBRBG这样的组合是可能的，即使第二个位置字母“重复”它们不会连续重复

因此，我想要一个函数，可以通过以下方式验证单词：

def validate(submitted_word, list_of_tuples)

一种可能性是构造此集合可能的序列的每个可能组合，以及第二个序列中的字母将产生的相应序列，过滤掉有效单词，然后过滤掉具有连续字母重复的单词，但我担心，考虑到元组列表可能会变得如此之大，这将变得效率低下

Answer 1

我们可以使用回溯，其中状态是每个字母使用的R、G、B的计数，以及在构造单词时选择的先前“RGB”

Python代码（未记忆）：

def f(i, word, prev, state):
  if i == len(word):
    return True

  letter = word[i]

  for second in ["R", "G", "B"]:
    if state[letter][second] and prev != second:
      state[letter][second] -= 1
      is_valid = f(i + 1, word, second, state)
      state[letter][second] += 1
      if is_valid:
        return True

  return False

def get_counts(tuples):
  result = {}
  for letter, rgb in tuples:
    if letter in result:
      result[letter][rgb] += 1
    else:
      result[letter] = {"R": 0, "G": 0, "B": 0}
      result[letter][rgb] = 1
  return result

tuples = [('A', 'R'), ('B', 'R'), ('C', 'G'), ('D', 'G'), ('E', 'B'), ('D', 'B'), ('R', 'B'), ('F', 'R'), ('V', 'R'), ('A', 'G')]

counts = get_counts(tuples)

print f(0, "ACE", "", counts) # True
print f(0, "ACED", "", counts) # True
print f(0, "BF", "", counts) # False