Leetcode — 두 문자열 간의 순열 차이

이 질문은 다음과 같은 의미를 지닌 간단한 질문입니다.

두 개의 문자열 s와 t가 주어지면 s의 각 문자는 최대 한 번 나타나고 t는 s의 순열입니다.

s와 t 사이의 순열 차이는 s에서 각 문자의 발생 인덱스와 t에서 해당 문자의 발생 인덱스 간의 절대 차이의 합으로 정의됩니다.

s와 t의 순열 차이를 반환합니다.

예 1:

입력: s = "abc", t = "bac"

출력: 2

설명:

s = "abc" 및 t = "bac"의 경우 s와 t의 순열 차이는 다음의 합과 같습니다.

의 "a" 발생 지수와 t의 "a" 발생 지수 간의 절대 차이입니다.

의 "b" 발생 지수와 t의 "b" 발생 지수 간의 절대 차이입니다.

s에서 "c" 발생 지수와 t에서 "c" 발생 지수 간의 절대 차이입니다.

즉, s와 t의 순열 차이는 |0 - 1|1 - 0 |2 - 2|입니다.

예 2:

입력: s = "abcde", t = "edbac"

출력: 12

설명: s와 t의 순열 차이는 |0 - 3| |1 - 2| |3 - 1 |4 - 0|입니다.

제약조건:

1 ≤ s.길이 ≤ 100

의 각 문자는 최대 한 번 나타납니다.

t는 s의 순열입니다.

에는 영문 소문자만 포함됩니다.

제목 설명이 길지만 예시를 보시면 제목의 목적을 더 쉽게 이해하실 수 있습니다.

순열 차이 계산 방법에 따라 다음 단계를 수행해야 합니다.

• 문자열 탐색
• 색인을 기준으로 문자 검색
• 두 번째 문자열에서 문자의 인덱스를 찾습니다.
• 첫 번째 색인에서 두 번째 색인을 뺍니다.
• 이 뺄셈의 절대값을 구하고 모든 결과를 하나의 출력으로 누적합니다.

이제 이 아이디어를 Java 코드로 변환해 보겠습니다.

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;
    }
}

실행 시간: 1ms, Java 온라인 제출의 100%보다 빠릅니다.

메모리 사용량: 42.67MB, Java 온라인 제출물의 57.64%보다 낮습니다.

성능이 좋은 솔루션입니다. 좀 더 우아하게 만들고 싶다면 스트리밍 처리를 사용하세요. 해결 방법은 다음과 같습니다.

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);
    }
}

런타임: 5ms, Java 온라인 제출의 2.31%보다 빠릅니다.

메모리 사용량: 43.02MB, Java 온라인 제출물의 23.05% 미만입니다.

성능과 메모리 측면에서 첫 번째 솔루션만큼 좋지는 않지만 더 우아합니다.

—

그렇습니다! 다른 질문이 있으면 언제든지 댓글을 남겨주시고, 제가 놓친 부분이 있으면 알려주시기 바랍니다. 그러면 그에 따라 업데이트할 수 있습니다.

다음 글에서 만나요! :)

위 내용은 Leetcode — 두 문자열 간의 순열 차이의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!