LeetCode 2575. Find the Divisibility Array of a String

周賽334。把word.length<=10^5看成word<=10^5，吃一發WA，好慘。

題目

輸入由n個數字組成的的字串word，還有正整數m。

div是word的可除性陣列，長度為n，且符合：

• 如果word[0,..,i]的的子字串轉成數字後可被m整除，則div[i] = 1
• 否則div[i] = 0

回傳word的可除性陣列。

解法

我們要在某個值val後面加上新的數字n，這個動作就是val*10+n。
初始化val為0，遍歷word中每個數字c，將c加到val尾端後檢查是否能被m整除，可以則為1；否則為0。

但是word中最多10^5個數字，很快就會使val溢位。

以例題二來看：

word = “1010”, m = 10
1%10==1, div[0]=0
10%10==0, div[1]=1
101%10==1, div[2]=0
1010%10==0, div[3]=1

1除10時=0餘1，之後不管商數0變成多少倍，一定都可以被m整除，因此只要保留餘數做處理。

word = “1010”, m = 10
1%10==1, r=1, div[0]=0
10%10==1, r=0, div[1]=1
1%10==1, r=1, div[2]=0
10%10==0, r=0, div[3]=1

時間複雜度O(N)。忽略答案陣列，空間複雜度O(1)。

class Solution:
    def divisibilityArray(self, word: str, m: int) -> List[int]:
        ans=[]
        val=0
        
        for c in word:
            val=(val*10+int(c))%m
            if val%m==0:
                ans.append(1)
            else:
                ans.append(0)
                
        return ans