package leetcode;

/**
 * https://leetcode.com/problems/freedom-trail/
 */
public class Problem514 {
    public int findRotateSteps(String ring, String key) {
        // TODO
        return findRotateSteps(ring, key, 0, 0);
    }

    private static int findRotateSteps(String ring, String key, int keyIdx, int startIdx) {
        if (keyIdx == key.length()) {
            return 0;
        }
        int count1 = 0;
        int i = startIdx;
        if (key.charAt(keyIdx) == ring.charAt(i)) {
            count1++;
        } else {
            while (key.charAt(keyIdx) != ring.charAt(i)) {
                i++;
                if (i == ring.length()) {
                    i = 0;
                }
                count1++;
            }
        }

        int count2 = 0;
        int j = startIdx;
        if (key.charAt(keyIdx) == ring.charAt(j)) {
            count2++;
        } else {
            while (key.charAt(keyIdx) != ring.charAt(j)) {
                j--;
                if (j == -1) {
                    j = ring.length() - 1;
                }
                count2++;
            }
        }
        int min = Math.min(count1, count2);
        int a = findRotateSteps(ring, key, keyIdx + 1, i) + min;
        int b = findRotateSteps(ring, key, keyIdx + 1, j) + min;
        min = Math.min(a, b);
        return min;
    }

    public static void main(String[] args) {
        Problem514 prob = new Problem514();
        System.out.println(prob.findRotateSteps("godding", "gd")); // 4
//        System.out.println(prob.findRotateSteps("godding", "gdo")); // 6
    }
}

@@ -164,15 +164,217 @@
     
-// TODO
+int%5B%5D%5B%5D memo = new int%5Bring.length()%5D%5Bkey.length()%5D;%0A        for (int i = 0; i %3C ring.length(); i++) %7B%0A           for (int j = 0; j %3C key.length(); j++) %7B%0A               memo%5Bi%5D%5Bj%5D = -1;%0A           %7D%0A        %7D
 %0A   
@@ -416,16 +416,22 @@
 ey, 0, 0
+, memo
 );%0A    %7D
@@ -520,16 +520,30 @@
 startIdx
+, int%5B%5D%5B%5D memo
 ) %7B%0A    
@@ -621,112 +621,104 @@
    i
-nt count1 = 0;%0A        int i = startIdx;%0A        if (key.charAt(keyIdx) == ring.charAt(i)) %7B%0A
+f (memo%5BstartIdx%5D%5BkeyIdx%5D != -1) %7B%0A            return memo%5BstartIdx%5D%5BkeyIdx%5D;%0A     
    
+%7D%0A
         
  cou
@@ -709,33 +709,38 @@
   %7D%0A        
+int
  count1
-++
+ = 1
 ;%0A        %7D 
@@ -733,37 +733,42 @@
  1;%0A        
-%7D else %7B%0A    
+int i = startIdx;%0A
         whil
@@ -826,21 +826,13 @@
     
-    
 i++;%0A
-    
     
@@ -857,36 +857,32 @@
 ing.length()) %7B%0A
-    
                 
@@ -896,34 +896,26 @@
             
-    %7D%0A    
+%7D%0A
             
@@ -920,38 +920,24 @@
   count1++;%0A
-            %7D%0A
         %7D%0A%0A 
@@ -956,17 +956,17 @@
 ount2 = 
-0
+1
 ;%0A      
@@ -989,103 +989,8 @@
 dx;%0A
-        if (key.charAt(keyIdx) == ring.charAt(j)) %7B%0A            count2++;%0A        %7D else %7B%0A    
     
@@ -1056,21 +1056,13 @@
     
- 
-   
 j--;%0A
-    
     
@@ -1100,20 +1100,16 @@
         
-    
 j = ring
@@ -1131,34 +1131,26 @@
             
-  
-  %7D%0A    
+%7D%0A
             
@@ -1171,68 +1171,10 @@
     
-    
 %7D%0A
-        %7D%0A        int min = Math.min(count1, count2);%0A
     
@@ -1225,23 +1225,32 @@
 x + 1, i
-) + min
+, memo) + count1
 ;%0A      
@@ -1303,15 +1303,24 @@
 1, j
-) + min
+, memo) + count2
 ;%0A  
@@ -1325,16 +1325,20 @@
         
+int 
 min = Ma
@@ -1363,262 +1363,57 @@
     
-return min;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem514 prob = new Problem514();%0A        System.out.println(prob.findRotateSteps(%22godding%22, %22gd%22)); // 4%0A//        System.out.println(prob.findRotateSteps(%22godding%22, %22gdo%22)); // 6
+memo%5BstartIdx%5D%5BkeyIdx%5D = min;%0A        return min;
 %0A   

Solve problem 514