如何开网店具体步骤_比较好的搜索引擎_长沙seo袁飞_山东移动网站建设

Description

Each character of the English alphabet has been mapped to a digit as shown below.

A string is divisible if the sum of the mapped values of its characters is divisible by its length.

Given a string s, return the number of divisible substrings of s.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: word = "asdf"
Output: 6
Explanation: The table above contains the details about every substring of word, and we can see that 6 of them are divisible.

Example 2:

Input: word = "bdh"
Output: 4
Explanation: The 4 divisible substrings are: "b", "d", "h", "bdh".
It can be shown that there are no other substrings of word that are divisible.

Example 3:

Input: word = "abcd"
Output: 6
Explanation: The 6 divisible substrings are: "a", "b", "c", "d", "ab", "cd".
It can be shown that there are no other substrings of word that are divisible.

Constraints:

1 <= word.length <= 2000
word consists only of lowercase English letters.

Solution

Simulation

Since the word length is not large, we could just generate all the substrings and see if its value is divisible by the length.

Time complexity: $o(n^2)$
Space complexity: $o(1)$

Prefix sum

Still didn’t get it after help…
…

Code

Simulation

class Solution:def countDivisibleSubstrings(self, word: str) -> int:chr_num = {'a': 1, 'b': 1, 'c': 2, 'd': 2, 'e': 2, 'f': 3, 'g': 3, 'h': 3, 'i': 4,'j':4,'k':4,'l':5,'m':5,'n':5,'o':6,'p':6,'q':6,'r':7,'s':7,'t':7,'u':8,'v':8,'w':8,'x':9,'y':9,'z':9}res = 0for i in range(len(word)):cur_sum = 0for j in range(i, len(word)):cur_sum += chr_num[word[j]]if cur_sum % (j - i + 1) == 0:res += 1return res

Prefix sum

class Solution:def countDivisibleSubstrings(self, word: str) -> int:chr_num = {'a': 1, 'b': 1, 'c': 2, 'd': 2, 'e': 2, 'f': 3, 'g': 3, 'h': 3, 'i': 4,'j':4,'k':4,'l':5,'m':5,'n':5,'o':6,'p':6,'q':6,'r':7,'s':7,'t':7,'u':8,'v':8,'w':8,'x':9,'y':9,'z':9}res = 0for i in range(1, 10):pre_sum = {0: 1}cur_sum = 0for word_i, each_word in enumerate(word):cur_sum += chr_num[each_word] - ires += pre_sum.get(cur_sum, 0)pre_sum[cur_sum] = pre_sum.get(cur_sum, 0) + 1return res