Freedom Trail

一次AC，没有任何优化的前提下超过53.97%。

开始试图用贪心，很快发现问题，找到下一个最近的字符A，而避开了某个距离更远的字符A，第二个字符B和距离更远的字符A挨着。很明显贪心就不适用了。依赖于之前某个解，当前解不一定是由上一最优解构成的时候，考虑用dp，当时搜索总是万能的。考虑到length最多到100，搜索可能不现实。

开始DP，这道题实际上很像vacations 那道dp，dp[i][j]代表match了i个key字符，停留在ring的第j个位置。最后的结果就是dp[key.length()]['d']的所有值中最小的。dp[i][j] = dp[i-1][t]+dist(t,j)+1; 这里t代表match key 第i-1个字符后，停留在位置t。所以我们不用枚举所用的t，只枚举停留的位置。用hashmap(character, ArrayList<Integer>) 存储可能停留的位置。

想到这里，思路就大体完成了。关于计算circular dist的时候，记得不要用绝对值，而用abs后另一个解是length－abs。square面试的时候犯了这个错误，非常感激面试官当时给我的面试表现给了五颗星。

滚动数组％2优化空间，记住在计算当前层的时候，需要intialize，清除之前的结果。不要在使用完后清算，可能会有问题，用前初始化一定没问题。

public class Solution {
    public int findRotateSteps(String ring, String key) {
        if(key==null || key.length()==0) return 0;
        int m = ring.length(); int n = key.length();
        HashMap<Character, ArrayList<Integer>> map = new HashMap<Character, ArrayList<Integer>>();
        for(int i=0;i<ring.length();i++){
            char c = ring.charAt(i);
            if(!map.containsKey(c)) map.put(c, new ArrayList<Integer>());
            map.get(c).add(i);
        }
        int[][] dp = new int[2][m+1]; for(int[] arr : dp) Arrays.fill(arr, Integer.MAX_VALUE); dp[0][0] = 0;
        for(int i=1;i<=n;i++){
            List<Integer> list = map.get(key.charAt(i-1));
            Arrays.fill(dp[i%2], Integer.MAX_VALUE);
            for(int j=0;j<list.size();j++){
                int idx = list.get(j);
                for(int t=0;t<m;t++){
                    if(dp[(i-1)%2][t]!=Integer.MAX_VALUE){
                        dp[i%2][idx] = Math.min(dp[i%2][idx], dp[(i-1)%2][t] + dist(t, idx, ring) +1);
                    }
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        List<Integer> list = map.get(key.charAt(n-1));
        for(int j=0;j<list.size();j++){
            ans = Math.min(ans, dp[n%2][list.get(j)]);
        }
        return ans;
    }

    public int dist(int t, int idx, String ring){
        int ans1 = Math.abs(t-idx);
        int ans2 = ring.length()-ans1;
        return Math.min(ans1, ans2);
    }

}

论坛上的concise解法，不能理解为什么从m-1 to 0而不是0 to m－1的枚举。

 public int findRotateSteps(String ring, String key) {
        int n = ring.length();
        int m = key.length();
        int[][] dp = new int[m + 1][n];

        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = 0; k < n; k++) {
                    if (ring.charAt(k) == key.charAt(i)) {
                        int diff = Math.abs(j - k);
                        int step = Math.min(diff, n - diff);
                        dp[i][j] = Math.min(dp[i][j], step + dp[i + 1][k]);
                    }
                }
            }
        }

        return dp[0][0] + m;
    }

Unique Substrings in Wraparound String

看清是dp以后快速撸了一个二维dp，dp[i][j]表示string(i, j)是否valid, hashset统计unique string。18/81后居然MLE了。很震惊，证明set存unique string的思路是错的，确实太多了。

public class Solution {
    public int findSubstringInWraproundString(String p) {
        if(p==null || p.length()==0)
            return 0;
        int n = p.length();
        boolean[][] dp = new boolean[n][n]; int ans = 0; HashSet<String> set = new HashSet<String>();
        for(int i=0;i<n;i++) {dp[i][i] = true; set.add(p.substring(i,i+1));}
        for(int l=2;l<=n;l++){
            for(int left =0;left+l-1<n;left++){
                int right = left+l-1;
                dp[left][right] = dp[left][right-1] && dp[left+1][right] && next(p.charAt(left), p.charAt(left+1)) && next(p.charAt(right-1), p.charAt(right));
                if(dp[left][right]) set.add(p.substring(left,right+1));
            }
        }
        return set.size();
    }

    public boolean next(char a, char b){
        return b== (((int)(a-'a')+1)%26)+'a';
    }
}

论坛上的一维dp加Math更巧妙。题目已知只有26个小写字母，我们可以统计道每个小写字母的最长长度，"abcd", "bcd"就不用重复计算了。注意“zab”这个corner case。运用数学知识，只要累加每个count[i]中的字符就可以了。