首页 > 试题广场 >

小红的字符串修改

[编程题]小红的字符串修改

热度指数：8493 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\,\,\,\,\,\,\,\,\,\,$ 小红有一个由小写字母构成的字符串 $s$ ，每次她可以把其中一个任意一个字母替换成其在字母表中相邻的字母，例如把 ' $a$ ' 替换成 ' $b$ ' 或者 ' $z$ '。现在小红想知道，最少需要替换多少次，使得 $s$ 成为 $t$ 的子串。

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

输入描述:

第一行输入一个长度不超过  ，且仅由小写字母构成的字符串  代表小红手中待替换的串。
第二行输入一个长度不小于  但不超过  ，且仅由小写字母构成的字符串  代表目标串。

输出描述:

在一行上输出一个整数，代表最少需要替换的次数。

示例1

输入

abc
abbc

输出

说明

需要进行一次替换，将 '' 替换成 '' ，此时得到 "" ，是 "" 的子串，因为本质上是由 "" 末尾删除了一个字符得到的。

示例2

输入

zzzzzz
xyzabc

输出

算法知识视频讲解

Python3

意若久时天然呆

import sys

s, t = sys.stdin.readline().strip(), sys.stdin.readline().strip()
ns, nt, m = len(s), len(t), -1
for i in range(nt - ns + 1):
    c = 0
    for j in range(ns):
        x = abs(ord(s[j]) - ord(t[i + j]))
        c += min(x, 26 - x)
    if (m == -1) + (c < m):
        m = c
print(m)

发表于 2026-01-20 15:13:37 回复(0)

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)

提交观点

问题信息

字符串模拟阿里云

难度：

4条回答 101收藏 1612浏览

小红的字符串修改

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

相关试题