[leetcode] 1540. Can Convert String in K Moves

Description

Given two strings s and t, your goal is to convert s into t in k moves or less.

During the ith (1 <= i <= k) move you can:

• Choose any index j (1-indexed) from s, such that 1 <= j <= s.length and j has not been chosen in any previous move, and shift the character at that index i times.
• Do nothing.

Shifting a character means replacing it by the next letter in the alphabet (wrapping around so that ‘z’ becomes ‘a’). Shifting a character by i means applying the shift operations i times.

Remember that any index j can be picked at most once.

Return true if it’s possible to convert s into t in no more than k moves, otherwise return false.

Example 1:

Input: s = "input", t = "ouput", k = 9
Output: true
Explanation: In the 6th move, we shift 'i' 6 times to get 'o'. And in the 7th move we shift 'n' to get 'u'.      

Example 2:

Input: s = "abc", t = "bcd", k = 10
Output: false
Explanation: We need to shift each character in s one time to convert it into t. We can shift 'a' to 'b' during the 1st move. However, there is no way to shift the other characters in the remaining moves to obtain t from s.      

Example 3:

Input: s = "aab", t = "bbb", k = 27
Output: true
Explanation: In the 1st move, we shift the first 'a' 1 time to get 'b'. In the 27th move, we shift the second 'a' 27 times to get 'b'.      

Constraints:

• 1 <= s.length, t.length <= 10^5
• 0 <= k <= 10^9
• s, t contain only lowercase English letters.

分析

• 如果題目看懂了之後，就會發現一個規律，字元串s和t中，相應位置的ascii的差剛好是需要移動的步數，然後k可以大于26，字元串移動是循環的。是以(t[i]-s[i])%26，剛好等于ascii大的字母移動到ascii小的字母的步數。
• 可能有些移動步數是一樣的，但是k可以大于26，是以用一個字典來統計相同移動步數的頻率，然後計算所有相同步數字元移動的步數否超過k就行了，超過k，傳回False，否則是符合題目要求的；
• 特别的對于不會移動的字元，移動步數為0，需要跳過。

代碼

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if(len(s)!=len(t)):
            return False
        n=len(s)
        d=collections.defaultdict(int)
        for i in range(n):
            val=(ord(t[i])-ord(s[i]))%26
            if(val==0):
                continue
            if(d[val]*26+val>k):
                return False
            d[val]+=1
        return True      

參考文獻