5469. K 次操作轉變字串
給你兩個字串 s 和 t ，你的目標是在 k 次操作以內把字串 s 轉變成 t 。
在第 i 次操作時（1 <= i <= k），你可以選擇進行如下操作：
選擇字串 s 中滿足 1 <= j <= s.length 且之前未被選過的任意下標 j （下標從 1 開始），並將此位置的字元切換 i 次。
不進行任何操作。
切換 1 次字元的意思是用字母表中該字母的下一個字母替換它（字母表環狀接起來，所以 ‘z’ 切換後會變成 ‘a’）。
請記住任意一個下標 j 最多隻能被操作 1 次。
如果在不超過 k 次操作內可以把字串 s 轉變成 t ，那麼請你返回 true ，否則請你返回 false 。
範例 1：
輸入：s = 「input」, t = 「ouput」, k = 9
輸出：true
解釋：第 6 次操作時，我們將 ‘i’ 切換 6 次得到 ‘o’ 。第 7 次操作時，我們將 ‘n’ 切換 7 次得到 ‘u’ 。
範例 2：
輸入：s = 「abc」, t = 「bcd」, k = 10
輸出：false
解釋：我們需要將每個字元切換 1 次才能 纔能得到 t 。我們可以在第 1 次操作時將 ‘a’ 切換成 ‘b’ ，但另外 2 個字母在剩餘操作中無法再轉變爲 t 中對應字母。
範例 3：
輸入：s = 「aab」, t = 「bbb」, k = 27
輸出：true
解釋：第 1 次操作時，我們將第一個 ‘a’ 切換 1 次得到 ‘b’ 。在第 27 次操作時，我們將第二個字母 ‘a’ 切換 27 次得到 ‘b’ 。
提示：
1 <= s.length, t.length <= 10^5
0 <= k <= 10^9
s 和 t 只包含小寫英文字母
** 注意，每次重複轉動的數值都要增加26.表示多一圈又轉到原始位置。**
class Solution:
def canConvertString(self, s: str, t: str, k: int) -> bool:
n = len(s)
m = len(t)
if n != m: return False
nums = [0]*n
for i in range(n):#計算兩個字元牀的差值（負數+26）
temp = ord(t[i]) - ord(s[i])
if temp >= 0:
nums[i] = temp
else:
nums[i] = 26+temp
# print(nums)
do = max(nums)#其中最大的次數
#預處理一下
if do > k:return False
dic = {}#建立一個字典，將次數不爲0的統計頻次
cnt = 0
for i in range(n):
if nums[i]!= 0:
if nums[i] not in dic:
dic[nums[i]] = 1
else:
dic[nums[i]] += 1
if nums[i] != 0:
cnt += 1
count = 0#統計完頻次之後，就選擇一個最多的轉動次數和k進行比較
for c in dic:
count = 26*(dic[c]-1)+c
if count > k:
# print('ok')
return False
return True
偷一偷肖總的程式碼：
class Solution:
def canConvertString(self, s: str, t: str, k: int) -> bool:
if len(s)!= len(t):
return False
has_oper = [0]*26
n = len(s)
for i in range(n):
a = ord(s[i])
b = ord(t[i])
if a != b:
cnt = b-a if a < b else 26-(a-b)
check = False
if has_oper[cnt-1]*26 + cnt <= k: #可以切換
has_oper[cnt-1] += 1
check = True
if not check:
return False
return True
作者：2547892696
鏈接：https://leetcode-cn.com/problems/can-convert-string-in-k-moves/solution/python3-shuang-bai-by-2547892696/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。