咨询：求解有效坑洼字符串数量的算法实现方案

问题分析 #

我们需要统计符合描述字符串的合法坑洼字符串（仅由P/非P组成）数量，核心是处理每个位置的约束——每个位置的描述字符依赖自身及左右邻居的状态。这类相邻约束问题适合用动态规划解决，通过状态压缩优化空间复杂度。

核心思路 #

1. 状态定义：用dp[i][a][b]表示处理到第i个字符时，第i-1位状态为a（0=非P，1=P）、第i位状态为b的合法方案数。通过状态压缩，只需维护前一步的2×2状态数组（prev_dp），无需保存整个DP表。
2. 约束判断：针对字符串的首字符、中间字符、尾字符分别定义约束判断规则，确保每一步状态转移符合描述要求。
3. 状态转移：遍历所有可能的前状态和当前状态，若符合中间字符的约束，则累加方案数到当前状态。
4. 边界处理：单独处理长度为1的字符串，以及首尾字符的特殊约束。

详细步骤 #

1. 约束规则定义

以下规则中，a为当前位置的左邻居状态，b为当前位置状态，c为右邻居状态：

• 首字符（位置0）：
  • 'P'：必须a=1（当前是P，右邻居无约束）
  • '0'：必须a=0且b=0（当前非P，右邻居也非P）
  • '1'：必须a=0且b=1（当前非P，右邻居是P）
  • '2'：不可能满足（无左邻居），直接返回0
  • '?'：允许a=1，或a=0且b=0，或a=0且b=1
• 尾字符（位置n-1）：
  • 'P'：必须c=1（当前是P，左邻居无约束）
  • '0'：必须c=0且b=0（当前非P，左邻居也非P）
  • '1'：必须c=0且b=1（当前非P，左邻居是P）
  • '2'：不可能满足（无右邻居），直接返回0
  • '?'：允许c=1，或c=0且b=0，或c=0且b=1
• 中间字符（位置k，0<k<n-1）：
  • 'P'：必须b=1（当前是P，左右邻居无约束）
  • '0'：必须b=0且a=0且c=0（当前非P，左右都非P）
  • '1'：必须b=0且a+c=1（当前非P，左右恰好一个是P）
  • '2'：必须b=0且a=1且c=1（当前非P，左右都是P）
  • '?'：允许b=1，或符合'0'/'1'/'2'的任意一种情况

2. 动态规划流程

• 初始化：针对首字符，遍历所有可能的前两位状态（a和b），初始化prev_dp数组。
• 状态转移：从第2位到倒数第2位，遍历所有前状态（a,b）和当前状态（c），若符合中间字符的约束，则更新当前状态数组curr_dp。
• 收尾计算：遍历最后两位的所有状态，若符合尾字符的约束，则累加方案数得到最终结果。

3. 空间优化

仅用两个2×2数组（prev_dp和curr_dp）存储状态，空间复杂度为O(1)，时间复杂度为O(n)（每个位置仅需遍历8种状态组合），完全适配n≤1e5的约束。

示例验证 #

以输入?01???为例：

1. 初始化prev_dp：首字符为?，4种状态均合法，初始值全为1。
2. 处理第2位（描述0）：仅(0,0,0)符合约束，prev_dp变为[[1,0],[0,0]]。
3. 处理第3位（描述1）：仅(0,0,1)符合约束，prev_dp变为[[0,1],[0,0]]。
4. 处理第4位（描述?）：(0,1,0)和(0,1,1)均合法，prev_dp变为[[0,0],[1,1]]。
5. 处理第5位（描述?）：4种状态均合法，prev_dp变为[[1,1],[1,1]]。
6. 收尾计算：尾字符为?，4种状态均符合约束，总方案数为4，与示例输出一致。

代码实现框架 #

MOD = 10**9 +7

def check_first(s0, a, b):
    if s0 == 'P':
        return a ==1
    elif s0 == '0':
        return a ==0 and b ==0
    elif s0 == '1':
        return a ==0 and b ==1
    elif s0 == '2':
        return False
    else: # '?'
        return (a ==1) or (a ==0 and b ==0) or (a ==0 and b ==1)

def check_last(s_last, b, c):
    if s_last == 'P':
        return c ==1
    elif s_last == '0':
        return c ==0 and b ==0
    elif s_last == '1':
        return c ==0 and b ==1
    elif s_last == '2':
        return False
    else: # '?'
        return (c ==1) or (c ==0 and b ==0) or (c ==0 and b ==1)

def check_mid(sk, a, b, c):
    if sk == 'P':
        return b ==1
    elif sk == '0':
        return b ==0 and a ==0 and c ==0
    elif sk == '1':
        return b ==0 and (a + c) ==1
    elif sk == '2':
        return b ==0 and a ==1 and c ==1
    else: # '?'
        return (b ==1) or (b ==0 and a ==0 and c ==0) or (b ==0 and (a +c)==1) or (b ==0 and a ==1 and c ==1)

def count_valid(s):
    n = len(s)
    if n ==1:
        if s[0] == 'P' or s[0] == '0':
            return 1
        elif s[0] == '1' or s[0] == '2':
            return 0
        else: # '?'
            return 2
    # 初始化prev_dp
    prev_dp = [[0]*2 for _ in range(2)]
    for a in range(2):
        for b in range(2):
            if check_first(s[0], a, b):
                prev_dp[a][b] =1
    # 检查是否初始就无合法方案
    if all(all(x==0 for x in row) for row in prev_dp):
        return 0
    # 处理中间字符
    for i in range(2, n):
        curr_dp = [[0]*2 for _ in range(2)]
        for a in range(2):
            for b in range(2):
                cnt = prev_dp[a][b]
                if cnt ==0:
                    continue
                for c in range(2):
                    if check_mid(s[i-1], a, b, c):
                        curr_dp[b][c] = (curr_dp[b][c] + cnt) % MOD
        prev_dp = curr_dp
        if all(all(x==0 for x in row) for row in prev_dp):
            return 0
    # 处理尾字符
    res =0
    for b in range(2):
        for c in range(2):
            cnt = prev_dp[b][c]
            if cnt ==0:
                continue
            if check_last(s[-1], b, c):
                res = (res + cnt) % MOD
    return res

T = int(input())
for _ in range(T):
    s = input().strip()
    print(count_valid(s))

内容的提问来源于stack exchange，提问作者Aman