难度: Medium
给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。
word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：
word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1div[i] = 0返回 word 的可整除数组。
示例 1：
输入：word = "998244353", m = 3 输出：[1,1,0,0,0,1,1,0,0] 解释：仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。
示例 2：
输入：word = "1010", m = 10 输出：[0,1,0,1] 解释：仅有 2 个前缀可以被 10 整除："10" 和 "1010" 。
提示：
1 <= n <= 105word.length == nword 由数字 0 到 9 组成1 <= m <= 109运行时间: 77 ms
内存: 19.0 MB
class Solution:
def divisibilityArray(self, word: str, m: int) -> List[int]:
res = []
cur = 0
for char in word:
cur = (cur * 10 + ord(char) - 48) % m
res.append(1 if cur== 0 else 0)
return res
这道题要求对于字符串 'word' 中的每个前缀，判断其转换成整数后是否能被 'm' 整除。直接计算每个前缀的整数值会非常耗时，尤其是前缀很长的情况。因此，题解采用了模运算的性质来逐步构建每个前缀的模 'm' 值。通过维护一个当前值 'cur'，每次读取一个新的字符，都将 'cur' 更新为 '(cur * 10 + 当前字符值) % m'。这样，'cur' 始终保持为当前前缀对 'm' 的模。如果 'cur' 为0，则说明当前前缀可以被 'm' 整除，反之则不能。这种方法避免了直接计算大数的除法，是一种时间效率和空间效率较高的解决方案。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def divisibilityArray(self, word: str, m: int) -> List[int]:
res = [] # 结果数组
cur = 0 # 当前前缀对 m 的余数
for char in word:
cur = (cur * 10 + ord(char) - 48) % m # 更新当前前缀的余数
res.append(1 if cur == 0 else 0) # 判断当前前缀是否能被 m 整除，并添加结果到数组
return res
这种表达式是为了逐步构建和更新字符串前缀所表示的数值的模`m`。其中，`ord(char) - 48`是将字符（假设是'0'到'9'的数字字符）转换成对应的整数值（例如，将字符'2'转换为整数2）。`cur * 10`是将当前已构建的数值左移一位（即数值乘以10），然后加上新的数字，形成新的更长的前缀数值。最后，取这个结果对`m`的模，得到当前前缀对`m`的余数。这种计算方式有效地避免了大整数的直接运算，同时利用模运算的性质（`(a * b) % c == ((a % c) * (b % c)) % c`），确保结果的正确性。
是的，这种更新方式能够确保在所有情况下正确表示前缀的模值。由于模运算的性质，每一步的`(cur * 10 + 数字) % m`计算都是基于之前的模值进行的，这保证了即使数值非常大，也能通过分步计算获得准确的模值。因此，`cur`的更新方式是有效且正确的，无论前缀有多长。
虽然输入的`m`值非常大可能会稍微影响计算效率，但由于现代计算机处理大整数的模运算相当高效，这种影响通常是可以接受的。模运算是一个快速的算术操作，即使对于较大的数字，现代处理器也能够快速执行。因此，即使`m`的值很大，该方法的效率仍然是较高的，不会有显著的性能下降。
当前算法假设字符串中只包含数字字符。如果字符串包含非数字字符，则`ord(char) - 48`的结果可能不是一个有效的0到9之间的数字，从而导致错误的计算。如果需要处理包含非数字字符的字符串，算法需要修改以先检测字符是否为数字。可以在计算前添加一个判断条件，例如使用`char.isdigit()`来检查字符是否为数字，如果不是数字，则可以跳过该字符或者将其处理为特定的逻辑（例如错误处理或返回特定结果）。