O(RK)-time DP solution


  • 5
    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();
        }
    }
    

  • 1
    B

    Why only need to check the index closest to left and to right? It seems to me that we need to check all indexes, since an index not closest left or right could have the lowest total number of moves.


Log in to reply
 

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