[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 = 9Output: trueExplanation: 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 = 10Output: falseExplanation: 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 = 27Output: trueExplanation: 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^50 <= k <= 10^9s, t contain only lowercase English letters.

分析

题目的意思是：给定字符串s和t，求s经过k步变换后能够得到t，其中第i步需要移动i个字符。

如果题目看懂了之后，就会发现一个规律，字符串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

参考文献

​​[LeetCode] [Java/Python 3] O(n) Count the shift displacement, w/ brief explanation and analysis.​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。