Hard

题目描述

给你一个由数字组成的字符串 s。

返回 s 中能被其非零最后一位数字整除的子字符串数量。

注意：子字符串可以包含前导零。

示例 1：

输入：s = "12936"

输出：11

解释：

子字符串 “29”、“129”、“293” 和 “2936” 不能被它们的最后一位数字整除。总共有 15 个子字符串，所以答案是 15 - 4 = 11。

示例 2：

输入：s = "5701283"

输出：18

解释：

子字符串 “01”、“12”、“701”、“012”、“128”、“5701”、“7012”、“0128”、“57012”、“70128”、“570128” 和 “701283” 都能被它们的最后一位数字整除。此外，所有只包含一个非零数字的子字符串都能被自己整除。因为有 6 个这样的数字，所以答案是 12 + 6 = 18。

示例 3：

输入：s = "1010101010"

输出：25

解释：

只有以数字 ‘1’ 结尾的子字符串才能被它们的最后一位数字整除。有 25 个这样的子字符串。

约束：

  • 1 <= s.length <= 10^5
  • s 只包含数字。

解题思路

这是一道需要用动态规划解决的字符串问题。核心思想是统计以每个位置结尾的子字符串中，有多少个能被该位置的数字整除。

思路分析：

对于每个位置 i，我们需要知道所有以位置 i 结尾的子字符串中，有多少个数字能被 s[i] 整除（如果 s[i] 不为0）。

使用动态规划的状态定义：dp[d][r] 表示以当前位置结尾、最后一位数字为 d 的子字符串中，模 d 的余数为 r 的子字符串数量。

算法步骤：

  1. 遍历字符串的每个位置
  2. 对于每个位置，更新所有可能的余数状态
  3. 当前位置的数字如果不为0，统计模该数字余数为0的子字符串数量
  4. 状态转移：对于每个数字 d 和余数 r，新的余数为 (r * 10 + current_digit) % d

优化：

  • 由于只需要前一个位置的状态，可以用滚动数组优化空间
  • 数字0需要特殊处理，因为不能作为除数

这种方法的时间复杂度是 O(n * 90)，其中90是所有可能的(数字,余数)对的数量总和。

代码实现

class Solution {
public:
    long long countSubstrings(string s) {
        int n = s.length();
        long long result = 0;
        
        // dp[d][r] = 以当前位置结尾，最后一位数字为d，模d余数为r的子字符串数量
        vector<vector<long long>> dp(10, vector<long long>(10, 0));
        vector<vector<long long>> newDp(10, vector<long long>(10, 0));
        
        for (int i = 0; i < n; i++) {
            int digit = s[i] - '0';
            
            // 清空新的dp数组
            for (int d = 1; d <= 9; d++) {
                for (int r = 0; r < d; r++) {
                    newDp[d][r] = 0;
                }
            }
            
            // 单独的当前数字作为子字符串
            if (digit != 0) {
                newDp[digit][0] = 1;
                result++;
            }
            
            // 从之前的状态转移
            for (int d = 1; d <= 9; d++) {
                for (int r = 0; r < d; r++) {
                    if (dp[d][r] > 0) {
                        int newR = (r * 10 + digit) % d;
                        newDp[d][newR] += dp[d][r];
                    }
                }
            }
            
            // 统计能被最后一位数字整除的子字符串
            if (digit != 0) {
                result += newDp[digit][0] - 1; // 减去单独的当前数字（已经统计过）
            }
            
            // 更新dp数组
            dp = newDp;
        }
        
        return result;
    }
};

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        result = 0
        
        # dp[d][r] = 以当前位置结尾，最后一位数字为d，模d余数为r的子字符串数量
        dp = [[0] * 10 for _ in range(10)]
        
        for i in range(n):
            digit = int(s[i])
            new_dp = [[0] * 10 for _ in range(10)]
            
            # 单独的当前数字作为子字符串
            if digit != 0:
                new_dp[digit][0] = 1
                result += 1
            
            # 从之前的状态转移
            for d in range(1, 10):
                for r in range(d):
                    if dp[d][r] > 0:
                        new_r = (r * 10 + digit) % d
                        new_dp[d][new_r] += dp[d][r]
            
            # 统计能被最后一位数字整除的子字符串
            if digit != 0:
                result += new_dp[digit][0] - 1  # 减去单独的当前数字（已经统计过）
            
            dp = new_dp
        
        return result

public class Solution {
    public long CountSubstrings(string s) {
        int n = s.Length;
        long result = 0;
        
        // dp[d,r] = 以当前位置结尾，最后一位数字为d，模d余数为r的子字符串数量
        long[,] dp = new long[10, 10];
        
        for (int i = 0; i < n; i++) {
            int digit = s[i] - '0';
            long[,] newDp = new long[10, 10];
            
            // 单独的当前数字作为子字符串
            if (digit != 0) {
                newDp[digit, 0] = 1;
                result++;
            }
            
            // 从之前的状态转移
            for (int d = 1; d <= 9; d++) {
                for (int r = 0; r < d; r++) {
                    if (dp[d, r] > 0) {
                        int newR = (r * 10 + digit) % d;
                        newDp[d, newR] += dp[d, r];
                    }
                }
            }
            
            // 统计能被最后一位数字整除的子字符串
            if (digit != 0) {
                result += newDp[digit, 0] - 1; // 减去单独的当前数字（已经统计过）
            }
            
            dp = newDp;
        }
        
        return result;
    }
}

var countSubstrings = function(s) {
    const n = s.length;
    let result = 0;
    
    // dp[d][r] = 以当前位置结尾，最后一位数字为d，模d余数为r的子字符串数量
    let dp = Array.from({length: 10}, () => Array(10).fill(0));
    
    for (let i = 0; i < n; i++) {
        const digit = parseInt(s[i]);
        let newDp = Array.from({length: 10}, () => Array(10).fill(0));
        
        // 单独的当前数字作为子字符串
        if (digit !== 0) {
            newDp[digit][0] = 1;
            result++;
        }
        
        // 从之前的状态转移
        for (let d = 1; d <= 9; d++) {
            for (let r = 0; r < d; r++) {
                if (dp[d][r] > 0) {
                    const newR = (r * 10 + digit) % d;
                    newDp[d][newR] += dp[d][r];
                }
            }
        }
        
        // 统计能被最后一位数字整除的子字符串
        if (digit !== 0) {
            result += newDp[digit][0] - 1; // 减去单独的当前数字（已经统计过）
        }
        
        dp = newDp;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n × 45) = O(n)
空间复杂度O(45) = O(1)

其中 n 是字符串长度，45 是所有可能的 (数字, 余数) 对的总数 (∑d=1^9 d = 45)。

相关题目