当前位置：首页 > article >正文

抓住问题的关键解决LeetCode第3337题字符串转换后的长度II

article 2024/11/5 8:52:44

3337.字符串转换后的长度II

难度：困难

问题描述：

给你一个由小写英文字母组成的字符串s，一个整数t表示要执行的转换次数，以及一个长度为26的数组nums。每次转换需要根据以下规则替换字符串s中的每个字符：

将s[i]替换为字母表中后续的nums[s[i]-'a']个连续字符。例如，如果s[i]='a'且nums[0]=3，则字符'a'转换为它后面的3个连续字符，结果为"bcd"。

如果转换超过了'z'，则回绕到字母表的开头。例如，如果s[i]='y'且nums[24]=3，则字符'y'转换为它后面的3个连续字符，结果为"zab"。

返回恰好执行t次转换后得到的字符串的长度。

由于答案可能非常大，返回其对109+7取余的结果。

示例1：

输入：s="abcyy",t=2,nums=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2]

输出：7

解释：

第一次转换(t=1)

'a'变为'b'因为nums[0]==1

'b'变为'c'因为nums[1]==1

'c'变为'd'因为nums[2]==1

'y'变为'z'因为nums[24]==1

第一次转换后的字符串为:"bcdzz"

第二次转换(t=2)

'b'变为'c'因为nums[1]==1

'c'变为'd'因为nums[2]==1

'd'变为'e'因为nums[3]==1

'z'变为'ab'因为nums[25]==2

第二次转换后的字符串为:"cdeabab"

字符串最终长度：字符串为"cdeabab"，长度为7个字符。

示例2：

输入：s="azbk",t=1,nums=[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]

输出：8

解释：

第一次转换(t=1)

'a'变为'bc'因为nums[0]==2

'z'变为'ab'因为nums[25]==2

'b'变为'cd'因为nums[1]==2

'k'变为'lm'因为nums[10]==2

第一次转换后的字符串为:"bcabcdlm"

字符串最终长度：字符串为"bcabcdlm"，长度为8个字符。

提示：

1<=s.length<=105

s仅由小写英文字母组成。

1<=t<=109

nums.length==26

1<=nums[i]<=25

问题分析：

根据题目的描述，对于字符串s的处理，不管是处理几遍，最终都要涉及到对字符串s中的每一个字符进行处理，因而我们对问题的处理分为三个层次：

对单个字符的处理。对单个字符的处理，要结合nums中的要求来进行，所以为此编制处理函数turner（c，nums），其功能是对于一个字符c，按照nums中的要求将其转换为一个字符串。比如：字符'z'按nums[25]==1的要求，则转变为'a'，若按nums[25]==2的规则，则转变为'ab'。
对一个字符串s进行处理。既然能够对单个字符c按nums中的规则进行转换，那就可以对字符串s中的每一个字符进行这种转换，进而实现对一个字符串的处理。函数turnall（s）可以实现这个功能，nums给定规则，返回一个按规则处理过后的新字符串。
循环处理解决遍数，问题就解决了。

程序如下：

#单个字符c按nums中的规则处理，转换为一个新的字符或字符串，并返回
def turner(c,nums):
    idx=ord(c)-97
    cc=nums[idx]
    a=[]
    for i in range(cc):
        a.append(chr((ord(c)-96)%26+97+i))
    return ''.join(a)

#对一个字符串s按nums中的要求进行转换，并返回转换后的结果
def turnall(s):
    a=[]
    for i in s:
        a.append(turner(i,nums))
    return ''.join(a)

#输入s、t和nums
s=input('pls input s=')
t=int(input('pls input t='))
nums=eval(input('pls input nums='))

#利用循环对s进行t遍处理，输出处理之后的字符串和字符串长度
for i in range(t):
    s=turnall(s)
print(s)
print(len(s))

运行实例一

pls input s=abccz

pls input t=2

pls input nums=[1,2,3,1,1,1,1,1,2,1,2,1,1,1,1,1,2,1,2,2,2,2,2,2,2,2]

cddefeefgefgbcd

运行实例二

pls input s=azbk

pls input t=1

pls input nums=[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]

bcabcdlm

感悟：

抓住解决问题的关键，问题就会迎刃而解。关键是如何使自己具备这种抓关键的能力。