难度: Medium
Submission
运行时间: 1596 ms
内存: 16.9 MB
class Solution:
def equalDigitFrequency(self, s: str) -> int:
n = len(s)
accus = [[0]*(n+1) for _ in range(10)]
ord0 = ord('0')
for i, c in enumerate(s, 1):
c = ord(c) - ord0
for d in range(10):
accus[d][i] = accus[d][i-1] + (c==d)
res = sum(accu[-1]>0 for accu in accus)
uniqs = set()
for l in range(n-1):
for r in range(l+1, n):
last = 0
for d in range(10):
diff = accus[d][r+1] - accus[d][l]
if diff:
if last and last != diff:
break
last = diff
else:
uniqs.add(s[l:r+1])
return res + len(uniqs)
Explain
题解首先采用预处理方式建立累积频率数组（accus），用于快速查询任何子字符串中每个数字字符的出现次数。这个二维数组的每一行代表一个数字（0-9），每一列的值代表从字符串开始到当前位置该数字的出现总次数。之后，解法通过遍历所有可能的子字符串，检查每个子字符串内所有数字的出现频率是否相同。如果一个子字符串中所有出现的数字的频率相同，则将其添加到集合中以避免重复计数。最终，函数返回独特满足条件的子字符串数量。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
class Solution:
def equalDigitFrequency(self, s: str) -> int:
n = len(s)
# 创建累积频率表
accus = [[0]*(n+1) for _ in range(10)]
ord0 = ord('0')
# 填充累积频率表
for i, c in enumerate(s, 1):
c = ord(c) - ord0
for d in range(10):
accus[d][i] = accus[d][i-1] + (c==d)
# 计算单个字符的子字符串数量
res = sum(accu[-1]>0 for accu in accus)
# 用于存储独特子字符串的集合
uniqs = set()
# 检查所有可能的子字符串
for l in range(n-1):
for r in range(l+1, n):
last = 0
for d in range(10):
diff = accus[d][r+1] - accus[d][l]
if diff:
if last and last != diff:
break
last = diff
else:
uniqs.add(s[l:r+1])
# 返回结果为单字符子串和独特子串的总和
return res + len(uniqs)
Explore
使用二维数组的目的是为了快速查询任何子字符串中的每个数字字符的出现次数。每一行代表一个数字（0-9），确保可以分别处理每个数字的出现频率。列数为字符串长度加一（n+1），是因为累积频率数组的第一列用于初始化，设为0，表示字符串开头前没有任何字符。这样可以方便地通过区间差计算出任何子字符串中每个数字的频率，即通过结束位置的频率减去开始位置之前的频率获得。
累积频率数组的更新方式是：对于字符串中的每个字符，首先将该字符对应的ASCII值转换为对应的数字索引（例如，字符'0'到'9'转换为索引0到9）。然后，对于每个数字0-9，更新它们在累积频率数组中的当前位置的值。具体地，如果当前字符对应的数字是d，则在d对应的行的当前列位置上的值，等于该行前一列的值加1；其他行的当前列的值，等于它们各自前一列的值。这样，每行的每列值都保持了从字符串开头到当前位置该数字的总出现次数。
单字符子字符串需要单独计算，因为这些子字符串自然满足所有字符频率相同的条件（只有一个字符）。直接通过累积频率数组的最后一列判断每个数字是否在整个字符串中至少出现一次，可以快速统计有多少种单字符子字符串。将这个数量加到其他满足条件的独特子字符串数量中，是因为这些单字符子字符串也是有效的符合条件的子字符串，应被计入总数。
在检查子字符串是否所有数字的出现频率相同时，逻辑是：首先计算子字符串中每个数字的出现次数，这可以通过累积频率数组快速完成（每个数字的出现次数等于该数字在子字符串结束位置加一的累积频率减去在子字符串开始位置的累积频率）。然后，遍历这些频率，比较第一个非零频率（即子字符串中至少出现一次的数字的频率）与其他非零频率是否相同。如果找到任何不同的频率，则当前子字符串不满足条件；如果所有非零频率相同，则该子字符串满足条件。