Leetcode — Permutation Difference between Two Strings

This is a simple question with the following meaning:

Given two strings s and t, each character in s appears at most once and t is a permutation of s.

The permutation difference between s and t is defined as the sum of the absolute differences between the index of occurrence of each character in s and the index of its occurrence in t.

Returns the permutation difference between s and t.

Example 1:

Input: s = "abc", t = "bac"

Output: 2

Explanation:

For s = "abc" and t = "bac", the difference in the permutations of s and t is equal to the sum of:

The absolute difference between the index of occurrence of "a" in

s and the index of occurrence of "a" in t.

The absolute difference between the index of occurrence of "b" in

s and the index of occurrence of "b" in t.

The absolute difference between the index of occurrence of "c" in

s and the index of occurrence of "c" in t.

That is, the permutation difference between s and t is equal to |0 - 1| |1 - 0| |2 - 2| = 2.

Example 2:

Input: s = "abcde", t = "edbac"

Output: 12

Explanation: The permutation difference between s and t is equal to |0 - 3| |1 - 2| |2 - 4| |3 - 1| |4 - 0| = 12.

Constraints:

1 ≤ s.length ≤ 100

Each character in

s appears at most once.

t is a permutation of s.

s only contain lowercase English letters.

The title description is lengthy, but looking at an example will make it easier to understand the goal of the title.

According to the calculation method of permutation difference, the following steps need to be performed:

• Traverse the string;
• Retrieve characters based on index;
• Find the index of the character in the second string;
• Subtract the second index from the first;
• Get the absolute value of this subtraction and accumulate all results into one output.

Now let’s convert this idea into Java code:

class Solution {
    public int findPermutationDifference(String s, String t) {
        int output = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int j = t.indexOf(c);
            output += Math.abs(i - j);
        }
        return output;
    }
}

Run time: 1ms, faster than 100% of Java online submissions.

Memory usage: 42.67 MB, lower than 57.64% of Java online submissions.

This is a solution with good performance. If you want to be more elegant, use streaming processing, the solution is as follows:

class Solution {
    public int findPermutationDifference(String s, String t) {
        return IntStream.range(0, s.length())
                   .map(i -> findCharPermutationDifference(s,t,i))
                   .sum();
    }

    public int findCharPermutationDifference(final String s, final String t, final int i) {
        final char c = s.charAt(i);
        final int j = t.indexOf(c);
        return Math.abs(i - j);
    }
}

Run time: 5ms, faster than 2.31% of Java online submissions.

Memory usage: 43.02 MB, less than 23.05% of Java online submissions.

Not as good as the first solution in terms of performance and memory, but more elegant.

—

That’s it! Please feel free to comment if you have any other questions and let me know if I've missed something so I can update accordingly.

See you in the next article! :)

The above is the detailed content of Leetcode — Permutation Difference between Two Strings. For more information, please follow other related articles on the PHP Chinese website!