```
public class Solution {
public int findRotateSteps(String ring, String key) {
int len = key.length();
//With current steps, the max number of chars can spell when stop at ring[i]
int[] dp = new int[ring.length()];
Arrays.fill(dp, -1); //-1 means can not be reached
int step = 0;
dp[0] = 0; //start position
while(true) {
step++;
int[] next = new int[ring.length()];
Arrays.fill(next, -1);
for(int i=0; i<dp.length; i++){
if(dp[i]<0){
continue; //can not reach current position
}
int left = i-1>=0? i-1 : dp.length-1;
next[left] = Math.max(next[left], dp[i]); //move left from i
int right = i+1<dp.length? i+1 : 0;
next[right] = Math.max(next[right], dp[i]); //move right from i
if(ring.charAt(i) == key.charAt(dp[i])){ //spell current char
dp[i]++;
if(dp[i] == len) return step;
next[i] = Math.max(next[i], dp[i]);
}
// no else, since if it's not a match, we won't stay
}
dp = next;
}
}
}
```