Another style of dfs and memorization, But TLE, just for fun...


  • 0

    I tried to memorize the step from current position on the metal dial to reach the current key needed in clockwise and counterclockwise. But sadly, TLE. :(

    public int findRotateSteps(String ring, String key) {
        int n = ring.length();
        int[][] clockwise = new int[n][26];
        int[][] countwise = new int[n][26];
        for(int i = 0;i<n;i++){
            for(int j = 0;j<26;j++){
                clockwise[i][j] = -1;
                countwise[i][j] = -1;
            }
        }
        int count = key.length();//press counted
        return search(ring,key,0,0,clockwise, countwise, count);
    }
    private int search(String ring, String key, int i, int j,int[][] clockwise,int[][] countwise, int count){
        int cw = 0;
        int cc = 0;
        if(j>=key.length()) return count;
        if(ring.charAt(i)==key.charAt(j)){
            return search(ring,key,i,j+1,clockwise, countwise,count);
        }
        int p = i;
        int q = i;
        if(clockwise[i][key.charAt(j)-'a']!=-1){
            cw = clockwise[i][key.charAt(j)-'a'];
        }
        else{
            while(ring.charAt(p)!=key.charAt(j)){
                if(clockwise[p][key.charAt(j)-'a']!=-1){
                    cw += clockwise[p][key.charAt(j)-'a'];
                    break;
                }
                p++;
                cw++;
                p = p%ring.length();
            }
            clockwise[i][key.charAt(j)-'a'] = cw;
        }
        if(countwise[i][key.charAt(j)-'a']!=-1){
            cc = countwise[i][key.charAt(j)-'a'];
        }
        else{
            while(ring.charAt(q)!=key.charAt(j)){
                if(countwise[q][key.charAt(j)-'a']!=-1){
                    cc+=countwise[q][key.charAt(j)-'a'];
                    break;
                }
                q--;
                cc++;
                q = (q + ring.length())%ring.length();
            }
            countwise[i][key.charAt(j)-'a'] = cc;
        }
        return Math.min(search(ring,key,(i+cw)%ring.length(),j+1,clockwise,countwise,cw+count), search(ring,key,(i-cc+ring.length())%ring.length(),j+1,clockwise,countwise,cc+count));
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.