输入:一个字符串ring首尾相连,表示一个圆盘的戒指,每个位置上都有一个字母与之对应,另一个字符串表示需要组合成的序列key。
要求:通过旋转ring来逐个匹配key中的字符,如果当前匹配成功,按下按钮,进行下一个字符的匹配,其中ring每旋转过一个字符,记录步数+1, 按下按钮步数+1。
输出:完全匹配key后,整个过程最少的步数
初一见整个题目莫名想起了电影《飞鹰计划》呢。。。
言归正传,第一感觉就是暴力dfs,求最小,但是感觉会超时,果不其然,提交了下面的代码之后,跑到第50个用例就不行了。。。
-
int findRotateSteps(string ring, string key){
-
int r_len = ring.length(), k_len = key.length(), i, j;
-
if(r_len == 0|| k_len == 0) return 0;
-
vector<vector<int>> dist(r_len, vector<int>(r_len, 0));
-
for(i = 0; i < r_len; i++)
-
for(j = i; j < r_len; j++)
-
dist[i][j]=dist[j][i]=min(j-i, i-j+r_len)+1;
-
return helper(ring, key, r_len, k_len, 0, 0, 0, dist);
-
}
-
int helper(string ring, string key, int r_len, int k_len, int r_idx, int k_idx, int cur_steps, vector<vector<int>>& dist){
-
if(k_idx == k_len)
-
return cur_steps;
-
int res = INT_MAX;
-
for(int i = 0; i < r_len; i++){
-
if(ring[i]==key[k_idx])
-
res = min(res, helper(ring, key, r_len, k_len, i, k_idx+1, cur_steps+dist[r_idx][i], dist));
-
}
-
return res;
-
}
脑壳疼。。。
想了半天,想到用dp,创建二维数组dist,其中每个元素的初始值设置为INT_MAX
其中dist[i][j]表示:使用ring[j]来匹配到key[i]时所用的最短步骤,递推如下:
dist[i][j] = min(dist[i][j], dist[i-1][k]+min(abs(k-j), ring.length()-abs(k-j))+1)条件是{dist[i-1][k]!=INT_MAX,0<=k
AC代码如下:
-
int findRotateSteps(string ring, string key){
-
int r_len = ring.length(), k_len = key.length(), i, j, k;
-
if(r_len == 0|| k_len == 0) return 0;
-
vector<vector<int>> dist(k_len, vector<int>(r_len, INT_MAX));
-
for( i = 0; i < r_len; i++)
-
if(ring[i]==key[0])dist[0][i]=min(i, r_len-i)+1;
-
for(i = 1; i < k_len; i++){
-
vector<int> temp(dist[i-1]);
-
for(j = 0; j < r_len; j++){
-
if(temp[j]!=INT_MAX){
-
for(k = 0; k < r_len; k++){
-
if(ring[k]==key[i]){
-
dist[i][k]=min(dist[i][k], temp[j]+min(abs(j-k), r_len-abs(j-k))+1);
-
}
-
}
-
}
-
}
-
}
-
int res = INT_MAX;
-
for(i = 0; i < r_len;i++)
-
res = min(res, dist[k_len-1][i]);
-
return res;
-
}
阅读(2124) | 评论(0) | 转发(0) |