首页 > 试题广场 >

小红的字符串修改

[编程题]小红的字符串修改
  • 热度指数：7546 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\,\,\,\,\,\,\,\,\,\,小红有一个由小写字母构成的字符串 s，每次她可以把其中一个任意一个字母替换成其在字母表中相邻的字母，例如把 'a' 替换成 'b' 或者 'z'。现在小红想知道，最少需要替换多少次，使得 s 成为 t 的子串。

\,\,\,\,\,\,\,\,\,\,如果字符串 t 可以通过从字符串 s 的开头删除若干（可能为零或全部）字符以及从结尾删除若干（可能为零或全部）字符得到，则字符串 t 是字符串 s 的子串。

输入描述:
\,\,\,\,\,\,\,\,\,\,第一行输入一个长度不超过 10^3 ，且仅由小写字母构成的字符串 s 代表小红手中待替换的串。
\,\,\,\,\,\,\,\,\,\,第二行输入一个长度不小于 s 但不超过 10^3 ，且仅由小写字母构成的字符串 t 代表目标串。


输出描述:
\,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，代表最少需要替换的次数。
示例1

输入

abc
abbc

输出

1

说明

\,\,\,\,\,\,\,\,\,\,需要进行一次替换，将 '\tt c' 替换成 '\tt b' ，此时得到 "\tt abb" ，是 "\tt abbc" 的子串，因为本质上是由 "\tt abbc" 末尾删除了一个字符得到的。
示例2

输入

zzzzzz
xyzabc

输出

9
算法知识视频讲解
添加回答
Python3
吃鸡蛋不吃鸡蛋黄_头像 吃鸡蛋不吃鸡蛋黄_
def replace_num(s1, s2): #入参 一样长度
    cont = 0
    for j in range(len(s1)):
        cont += min(abs(ord(s2[j])-ord(s1[j])),26-abs(ord(s2[j])-ord(s1[j]))) #ord()字母转ascii
    return cont

def main():
    s1 = input().strip()
    s2 = input().strip()
    min_cont = float('inf') #定义无穷大的数保证记录第一次的值

    if len(s2)>len(s1):
        for i in range(len(s2)-len(s1)+1): #子串的可能个数  s1=abc s2=abcd 子串：abc bcd
            replc_cont = replace_num(s1,s2[i:i+len(s1)])
            if replc_cont < min_cont:
                min_cont = replc_cont #更新最小次数
    else: #两字符串相等的情况
        replc_cont = replace_num(s1,s2)
        if replc_cont < min_cont:
            min_cont = replc_cont #更新最小次数
    print(min_cont)

if __name__ == "__main__":
    main()
发表于 2025-09-23 17:37:38 回复(0)
Python3
忧伤的双曲线头像 忧伤的双曲线
def times(s1,s2):
    #在这里输入确保s1和s2长度相同
    count = 0
    for i in range(len(s1)):
        count += min(abs(ord(s1[i])-ord(s2[i])),26-abs(ord(s1[i])-ord(s2[i])))
    return count

s = input()
t = input()

len_s = len(s)
len_t = len(t)
min_times = 1e5
for start in range(len_t):
    if (start+len_s)<=len_t:
        tmp_times = times(s,t[start:start+len_s])
        if tmp_times<min_times:
            min_times = tmp_times
    else:
        break

print(min_times)
发表于 2025-08-24 15:56:23 回复(0)
提交观点

问题信息

字符串 模拟 阿里云
难度：
2条回答 1316浏览

热门推荐

相关试题

小红的字符串修改

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号