要求:通过旋转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,0AC代码如下:
点击(此处)折叠或打开
- 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;
- }