O(RK)-time DP solution


  • 4
    L

    We can further improve the runtime of this DP Solution from O(R * R * K) to O(R * (26 + K)) = O(RK), where R = |Ring| and K = |Key|. Basically, we can do the inner-most loop in O(1) time. The idea is that if we are currently at position i and require the previous char equal to some letter ch, we just need to check the position (with letter ch) that is closest to i from its left or right. Thus, at most two positions need to be checked, instead of the entire ring.

    Update: The preprocessing of the following code takes O(R^2 * 26) = O(R^2) time. But I believe there must exist a faster way, and I was just too lazy to do that...
    Update: Okay, the preprocessing can be done in O(26 * R) = O(R) time.

    public int findRotateSteps(String ring, String key) {
        int R = ring.length(), K = key.length();
        int[][] prev = new int[R][26], next = new int[R][26];
        for (int i = 0; i < R; i++) {
            Arrays.fill(prev[i], -1);
            Arrays.fill(next[i], -1);
            for (int j = (i + 1) % R; j != i; j = (j + 1) % R) {
                int ch = ring.charAt(j) - 'a';
                if (next[i][ch] == -1) next[i][ch] = j;
            }
            for (int j = (i - 1 + R) % R; j != i; j = (j - 1 + R) % R) {
                int ch = ring.charAt(j) - 'a';
                if (prev[i][ch] == -1) prev[i][ch] = j;
            }
            prev[i][ring.charAt(i) - 'a'] = next[i][ring.charAt(i) - 'a'] = i;
        }
    
        int[][] f = new int[K][R];
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < R; j++) {
                f[i][j] = Integer.MAX_VALUE / 2;
    
                if (key.charAt(i) == ring.charAt(j)) {
                    if (i == 0) f[i][j] = Math.min(f[i][j], dist(0, j, ring.length()));
                    else {
                        int preKey = key.charAt(i - 1) - 'a';
                        f[i][j] = Math.min(f[i][j], f[i - 1][prev[j][preKey]] + dist(prev[j][preKey], j, ring.length()));
                        f[i][j] = Math.min(f[i][j], f[i - 1][next[j][preKey]] + dist(next[j][preKey], j, ring.length()));
                    }
                }
                if (i == K - 1) ans = Math.min(ans, f[i][j]);
            }
        }
        return ans + K;
    }
    

    An O(26R) = O(R)-time preprocessing.

    int R = ring.length(), K = key.length();
    int[][] prev = new int[R][26], next = new int[R][26];
    Map<Character, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < ring.length(); i++) {
        char ch = ring.charAt(i);
        map.putIfAbsent(ch, new ArrayList<>());
        map.get(ch).add(i);
    }
    for (char ch : map.keySet()) {
        List<Integer> list = map.get(ch);
        for (int i = 0, ptr = 0; i < ring.length(); i++) {
            next[i][ch - 'a'] = list.get(ptr);
            prev[i][ch - 'a'] = list.get((ptr - 1 + list.size()) % list.size());
            if (ring.charAt(i) == ch) ptr = (ptr + 1) % list.size();
        }
    }
    

Log in to reply
 

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