leetcode1540. K 次操作轉(zhuǎn)變字符串

給你兩個(gè)字符串 s 和 t ，你的目標(biāo)是在 k 次操作以內(nèi)把字符串 s 轉(zhuǎn)變成 t 。

在第 i 次操作時(shí)（1 <= i <= k），你可以選擇進(jìn)行如下操作：

• 選擇字符串 s 中滿足 1 <= j <= s.length 且之前未被選過的任意下標(biāo) j （下標(biāo)從 1 開始），并將此位置的字符切換 i 次。
• 不進(jìn)行任何操作。

切換 1 次字符的意思是用字母表中該字母的下一個(gè)字母替換它（字母表環(huán)狀接起來，所以 'z' 切換后會(huì)變成 'a'）。

請(qǐng)記住任意一個(gè)下標(biāo) j 最多只能被操作 1 次。

如果在不超過 k 次操作內(nèi)可以把字符串 s 轉(zhuǎn)變成 t ，那么請(qǐng)你返回 true ，否則請(qǐng)你返回 false 。

示例 1：

輸入：s = "input", t = "ouput", k = 9
輸出：true
解釋：第 6 次操作時(shí)，我們將 'i' 切換 6 次得到 'o' 。第 7 次操作時(shí)，我們將 'n' 切換 7 次得到 'u' 。

示例 2：

輸入：s = "abc", t = "bcd", k = 10
輸出：false
解釋：我們需要將每個(gè)字符切換 1 次才能得到 t 。我們可以在第 1 次操作時(shí)將 'a' 切換成 'b' ，但另外 2 個(gè)字母在剩余操作中無法再轉(zhuǎn)變?yōu)?t 中對(duì)應(yīng)字母。

示例 3：

輸入：s = "aab", t = "bbb", k = 27
輸出：true
解釋：第 1 次操作時(shí)，我們將第一個(gè) 'a' 切換 1 次得到 'b' 。在第 27 次操作時(shí)，我們將第二個(gè)字母 'a' 切換 27 次得到 'b' 。

提示：

• 1 <= s.length, t.length <= 10^5
• 0 <= k <= 10^9
• s 和 t 只包含小寫英文字母。

---

方法：計(jì)數(shù)

思路：

本題使用計(jì)數(shù)的方法完成。對(duì)于每個(gè)需要改變的字符，它應(yīng)該切換幾次到達(dá)目標(biāo)字符，取決于t[i]和s[i]之間的差，

• 如果t[i]對(duì)應(yīng)字符在s[i]字符的后面，那么它需要的切換次數(shù)即為ord(t[i])-ord(s[i])
• 否則，需要切換的次數(shù)為ord(t[i])-ord(s[i])+26

因此，每個(gè)字符需要切換的次數(shù)均為0-25，因此我們使用一個(gè)長(zhǎng)度為26的數(shù)組nums，保存需要切換i次的字符的個(gè)數(shù)。

因?yàn)槲覀冎荒茉诘趇次操作的時(shí)候，切換i次，因此，如果nums[1] = 3，即有3個(gè)字符需要切換1次，那么我們只能在第1次操作、第27次操作和第53次操作將它們解決，即26*(nums[i]-1)+i。

因此我們對(duì)nums中的所有數(shù)進(jìn)行遍歷，根據(jù)上面公式，找到最大的值，跟k進(jìn)行比較，返回。

還要注意的是，最開始如果s和t的長(zhǎng)度不一樣，直接返回False。

代碼：

Python3：

class Solution:def canConvertString(self, s: str, t: str, k: int) -> bool:# 如果長(zhǎng)度不一樣，直接Falsen = len(s)m = len(t)if n != m:return False# 初始化numsnums = [0]*26# 遍歷填寫numsfor i in range(n):delta = ord(t[i])-ord(s[i])if delta >= 0:nums[delta] += 1else:nums[delta+26] += 1# 初始化need，需要的次數(shù)need = 0# 開始更新needfor i in range(1,26):temp = max(0,26*(nums[i]-1)+i)need = max(need,temp)return need <= k

cpp：

class Solution {
public:bool canConvertString(string s, string t, int k) {// 如果長(zhǎng)度不一樣，直接Falseint n = s.size();int m = t.size();if (n != m)return false;// 初始化numsvector<int>nums(26,0);// 遍歷填寫numsfor (int i = 0; i < n; ++i){int delta = t[i]- s[i];if (delta >= 0)nums[delta] ++;elsenums[delta+26] ++;}// 初始化need，需要的次數(shù)int need = 0;// 開始更新needfor (int i = 1; i < 26; ++i){int temp = max(0,26*(nums[i]-1)+i);need = max(need,temp);}            return need <= k;}
};

結(jié)果：

總結(jié)

以上是生活随笔為你收集整理的将输入字符串t中从第m个字符开始的全部字符复制到字符串s中_leetcode第32双周赛第二题leetcode1540. K 次操作转变字符串...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。