2021년 3월 LeetCoding Challenge — 6일차: 짧은 단어 인코딩

오늘은 3월 리트코딩 챌린지 6번째 문제를 풀어보겠습니다.

문제 설명

단어 배열의 유효한 인코딩은 다음과 같은 참조 문자열 및 인덱스 배열입니다.

words.length == indexes.length

참조 문자열 s는 '#' 문자로 끝납니다.

각 인덱스 indices[i]에 대해 indices[i]에서 시작하여 다음 '#' 문자까지(포함되지 않음) s의 하위 문자열은 words[i]와 같습니다.

단어 배열이 주어지면 유효한 단어 인코딩에서 가능한 가장 짧은 참조 문자열 s의 길이를 반환합니다.

예 1:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

예 2:

Input: words = ["t"]
Output: 2
Explanation: A valid encoding would be s = "t#" and indices = [0].

제약:

1 <= 단어 길이 <= 2000

1 <= 단어[i].길이 <= 7

words[i]는 소문자로만 구성됩니다.

해결책

질문에 따르면 주어진 문자열을 주어진 문자열 배열의 모든 단어를 포함하는 하나의 문자열로 인코딩해야 합니다. 출력 문자열의 길이를 최소화할 수 있는 방식으로 수행해야 합니다. 문자열을 다른 문자열과 겹치는 것은 허용됩니다. 또한 각 문자열 뒤에 #을 추가해야 합니다.

이 문제에 대한 알고리즘을 살펴보겠습니다. 여기서 우리는 주어진 모든 문자열을 저장하기 위해 Hashset을 사용했습니다. 단어의 문자가 겹치는지 확인하고 문자가 겹치면 해당 문자열을 삭제합니다. (이 단계는 예제를 통해 더 잘 이해할 수 있습니다.) 마지막으로 Hashset에 있는 문자열을 추가하고 #을 추가합니다.

코드는 다음과 같습니다.

n이 문자열 배열의 길이이고 k가 가장 긴 문자열의 길이이면

시간 복잡도: O(n*k)

공간 복잡도: O(n)

코드는 다음 저장소에서 찾을 수 있습니다.

2021년 3월 리트코딩 챌린지 이전 문제를 모두 올렸습니다. 확인하실 수 있습니다.

<올>

March LeetCoding Challenge — Day 1 — Distribute Candies

March LeetCoding Challenge — Day 2— Set Mismatch

March LeetCoding Challenge — Day 3 — Missing Number

March LeetCoding Challenge — Day 4 — Intersection of Two Linked Lists

March LeetCoding Challenge — Day 5 — Average of Levels in Binary Tree