题目描述：
给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。
最初，ring的第一个字符与 12:00 方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。
旋转 ring拼出 key字符 key[i] 的阶段中：
您可以将 ring顺时针或逆时针旋转 一个位置 ，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。
如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key的下一个字符（下一阶段）, 直至完成所有拼写。
数据范围：
$1\le ring.len, key.len \le 100$
保证有解
题解：
dp解法：
二维序列，使用 $dp[i][j]$ 表示状态 $key[i], ring[j]$ 的最小步数，则 $dp[i][j]$ 需要从 $dp[i-1][k]$ 转移过来，其中 $k$ 需要满足 $ring[k] = key[k]$ 。可以先用一个二维数组记录每个字母的位置， $pos[i][j]$ 表示字母 $i$ 第 $j$ 次出现的位置，将每个字母的位置记录下来。可以得到方程
初始条件：
将 $dp[i][j]$ 初始化为 $\infty$ ，然后需要初始化 $dp[0]$ ，对于每一个和 $key[0]$ 相等的位置，初始化 $dp[0]$ .
最短路解法：
使用 $(i, j, step)$ 表示状态， $dis[i][j]$ 表示到达 $key[i], ring[j]$ 的距离。然后使用优先级队列存状态。对于一个点 $(i, j)$ 需要找出边，出边就是 $pos[key[i + 1]]$ ，使用dijkstra的方式更新。
代码：
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int dp[maxn][maxn];
vector<vector<int>> pos;
int findRotateSteps(string ring, string key)
{
pos.resize(26);
int n = key.size(), m = ring.size();
for (int i = 0; i < m; ++i)
pos[ring[i] - 'a'].emplace_back(i);
for (int i = 0; i < pos[key[0]].size(); ++i)
{
int j = pos[key[0] - 'a'][i];
dp[0][j] = min(j, n - j) + 1;
}
int ans = INF;
for (int i = 1; i < n; ++i)
{
for (auto &j : pos[key[i] - 'a'])
{
for (auto &k : pos[key[i - 1] - 'a'])
{
dp[i][j] = min(dp[i][j], dp[i - 1][k] + min(abs(j - k), n - abs(j - k)) + 1);
}
if (i == n - 1)
ans = min(ans, dp[i][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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e2 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<vector<int>> pos;
int dis[maxn][maxn];
bool vis[maxn][maxn];
struct Node
{
int i, j, step;
bool operator<(const Node &p) const
{
return step > p.step;
}
Node(int i, int j, int step) : i(i), j(j), step(step) {}
};
int findRotateSteps(string ring, string key)
{
pos.resize(26);
int n = key.size(), m = ring.size();
for (int i = 0; i < m; ++i)
pos[ring[i] - 'a'].emplace_back(i);
priority_queue<Node> q;
int step;
memset(dis, 0x3f, sizeof(dis));
for (auto &j : pos[key[0] - 'a'])
{
step = min(j, m - j) + 1;
q.emplace(Node(0, j, step));
dis[0][j] = step;
}
int ans = INF;
while (q.size())
{
auto out = q.top();
q.pop();
if (out.i == n - 1)
break;
if (vis[out.i][out.j])
continue;
vis[out.i][out.j] = true;
if (out.i + 1 >= n)
break;
for (auto &j : pos[key[out.i + 1] - 'a'])
{
int w = min(abs(out.j - j), m - abs(out.j - j)) + 1;
if (dis[out.i + 1][j] > dis[out.i][out.j] + w)
{
dis[out.i + 1][j] = dis[out.i][out.j] + w;
if (out.i + 1 == n - 1)
ans = min(ans, dis[out.i + 1][j]);
q.push(Node(out.i + 1, j, dis[out.i + 1][j]));
}
}
}
return ans;
}
};
|