🔢字串應用: 數字和 Sum of Digits of String After Convert_LC #1945

dominik hofbauer on Unsplash

題目敘述 1945. Sum of Digits of String After Convert

給定一個由小寫字母組成的字串 s ，以及一個整數 k 。

首先，用英文字母順序的位置替換每個字母，將 s 轉換 為整數
（也就是，'a' 用 1 替換，'b' 用 2 替換，... 'z' 用 26 替換）。

接著，將整數 轉換 成 digit sum 。共重複 轉換 操作 k 次 。

例如，如果 s = "zbax" 且 k = 2 ，那麼執行下述步驟後得到的結果是整數 8 ：

英文替換成數字："zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124

轉換 #1：262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17

轉換 #2：17 ➝ 1 + 7 ➝ 8

請根據給定的s, k，執行對應的替換和轉換操作後，將得到的整數回傳。

測試範例

Example 1:

Input: s = "iiii", k = 1
Output: 36
Explanation: The operations are as follows:

- Convert: "iiii" ➝ "(9)(9)(9)(9)" ➝ "9999" ➝ 9999
- Transform #1: 9999 ➝ 9 + 9 + 9 + 9 ➝ 36
Thus the resulting integer is 36.

Example 2:

Input: s = "leetcode", k = 2
Output: 6
Explanation: The operations are as follows:

- Convert: "leetcode" ➝ "(12)(5)(5)(20)(3)(15)(4)(5)" ➝ "12552031545" ➝ 12552031545
- Transform #1: 12552031545 ➝ 1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 ➝ 33
- Transform #2: 33 ➝ 3 + 3 ➝ 6
Thus the resulting integer is 6.

Example 3:

Input: s = "zbax", k = 2
Output: 8

約束條件

Constraints:

• 1 <= s.length <= 100

字串s的長度介於1~100之間。

• 1 <= k <= 10

參數k介於1~10之間。

• s consists of lowercase English letters.

s只會有小寫英文字母。

演算法 拆分每個位置，進行相加

迭代掃描字串s的每個英文字母，替換成對應的數字。

接著拆分每個位置，將每個數字相加得到digit sum，反覆迭代k次，得到最終答案。

程式碼 拆分每個位置，進行相加

class Solution:
    def getLucky(self, s: str, k: int) -> int:

        # English letter to digits
        s = ''.join(str(ord(c) - ord('a') + 1) for c in s)

        # Compute digit sum k times
        for _ in range(k):

            t = sum(int(c) for c in s)
            s = str(t)
            
        return int(s)

複雜度分析

時間複雜度: O(n k)

輸入總共n個字元，計算digit sum時需要迭代k次。

空間複雜度: O(1)

所用到的都是固定大小的臨時變數，所需空間為O(1)

Reference:

[1] Sum of Digits of String After Convert - LeetCode