题目描述

输入小写元素组成的字符串str，再输入小写元素组成的需要查找的子串substr（保证子串中的字符至少在str中出现一次）
需要移动游标，现给出两个字符串和游标的初始位置，以最少的步数移动游标找到子串在母串的位置。游标可以向左移动一格或者向右移动一格，移动到边界可以循环至另一头

输入格式

aemoyn
amo
0

输出格式

3

题目分析

str长度为m，substr长度为n
用dp来做
dp[i][j]表示从前往后拼写出str的第i个字符，substr的第j个字符与游标对齐的最小步数（因为可以越过边界循环，需要注意abs）

(1) dp[i][j] = min(dp[i-1][k]+min{abs(j-k),n-abs(j-k)})  枚举所有 ring[k] == key[i-1]
1

最后的答案dp[n-1][j] , j=0~m-1
初始化
dp[0][k]=min(min{abs(k),n-abs(k)}),ring[k] == key[0]

代码如下：

以leetcode为例，每次遍历多+1

from math import inf
class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        m=len(ring)
        n=len(key)
        dp=[[inf]*m for _ in range(n)]
        # 保存所有字符对应位置
        mydict=dict()
        for i,r in enumerate(ring):
            if r in mydict:
                mydict[r].append(i)
            else:
                mydict[r]=[i]
        # 初始化dp第一维
        for k in mydict[key[0]]:
            dp[0][k]=min(abs(0-k),m-abs(0-k))+1

        for i in range(1,n):
            for j in range(m):
                for k in mydict[key[i-1]]:
                    if key[i]==ring[j]:
                        dp[i][j]=min(dp[i][j],dp[i-1][k]+min(abs(j-k),m-abs(j-k))+1)
        ans=inf
        for j in range(m):
            ans=min(ans,dp[n-1][j])
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

参考文献

https://www.nowcoder.com/discuss/629482?type=post&order=time&pos=&page=1&channel=-1&source_id=search_post_nctrack

leetcode514