514. Freedom Trail

Naive DP 
Can be optimized by iterating from key.length() - 1 to 0
这样可以省略i == 0的初始化和最后的stream

n -> ring.length(), m -> key.length()
Time O(mnn)
Space O(mn)

Without lambda
72.89 %

With lambda
21.61 %
class Solution {
    public int findRotateSteps(String ring, String key) {
        // ring = "godding", key = "gd"
        if (ring == null || key == null) {
            return 0;
        }
        // dp[i] -> min steps to take to dial key -> [0, i)
        // dp[i - 1][j] -> j positions have ring.charAt(j) == key.charAt(i - 1)
        // for all j -> min dp[i - 1][j] + j to all chars ring.charAt(k) == key.charAt(i)
        int[][] dp = new int[key.length()][ring.length()];
        int n = ring.length();
        for (int i = 0; i < key.length(); i++) {
            for (int j = 0; j < n; j++) { // find the position of key.charAt(i) on the ring
                int min = Integer.MAX_VALUE;
                if (ring.charAt(j) == key.charAt(i)) {
                    if (i == 0) {
                        // pos == 0
                        dp[i][j] = Math.min(j, n - j);
                        continue;
                    }
                    for (int pos = 0; pos < n; pos++) {
                        if (dp[i - 1][pos] != -1) {
                            int diff = Math.abs(pos - j);
                            min = Math.min(min, dp[i - 1][pos] + Math.min(diff, n - diff));
                        }
                    }
                    dp[i][j] = min;
                } else {
                    dp[i][j] = -1;
                }
            }
        }
        return key.length() + IntStream.of(dp[key.length() - 1]).filter(num -> num != -1).min().getAsInt();
    }
}