[리트코드] 1807 - Evaluate the Bracket Pairs of a String

1807. Evaluate the Bracket Pairs of a String

Medium

---

You are given a string s that contains some bracket pairs, with each pair containing a non-empty key.

• For example, in the string "(name)is(age)yearsold", there are two bracket pairs that contain the keys "name" and "age".

You know the values of a wide range of keys. This is represented by a 2D string array knowledge where each knowledge[i] = [keyi, valuei] indicates that key keyi has a value of valuei.

You are tasked to evaluate all of the bracket pairs. When you evaluate a bracket pair that contains some key keyi, you will:

• Replace keyi and the bracket pair with the key's corresponding valuei.
• If you do not know the value of the key, you will replace keyi and the bracket pair with a question mark "?" (without the quotation marks).

Each key will appear at most once in your knowledge. There will not be any nested brackets in s.

Return the resulting string after evaluating all of the bracket pairs.

 

Example 1:

Input: s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
Output: "bobistwoyearsold"
Explanation:
The key "name" has a value of "bob", so replace "(name)" with "bob".
The key "age" has a value of "two", so replace "(age)" with "two".

Example 2:

Input: s = "hi(name)", knowledge = [["a","b"]]
Output: "hi?"
Explanation: As you do not know the value of the key "name", replace "(name)" with "?".

Example 3:

Input: s = "(a)(a)(a)aaa", knowledge = [["a","yes"]]
Output: "yesyesyesaaa"
Explanation: The same key can appear multiple times.
The key "a" has a value of "yes", so replace all occurrences of "(a)" with "yes".
Notice that the "a"s not in a bracket pair are not evaluated.

 

Constraints:

• 1 <= s.length <= 105
• 0 <= knowledge.length <= 105
• knowledge[i].length == 2
• 1 <= keyi.length, valuei.length <= 10
• s consists of lowercase English letters and round brackets '(' and ')'.
• Every open bracket '(' in s will have a corresponding close bracket ')'.
• The key in each bracket pair of s will be non-empty.
• There will not be any nested bracket pairs in s.
• keyi and valuei consist of lowercase English letters.
• Each keyi in knowledge is unique.

분류

배열, 해시 테이블, 문자열

---

문제 풀이

1807. Evaluate the Bracket Pairs of a String 문제 풀이

문제 분석

주어진 문자열 s는 소괄호 ()로 둘러싸인 키(key)들을 포함할 수 있습니다. knowledge라는 2차원 문자열 배열은 각 키에 해당하는 값을 제공합니다. 문제의 목표는 문자열 s에서 소괄호로 둘러싸인 모든 키를 해당 knowledge에서 찾은 값으로 치환하는 것입니다. 만약 특정 키에 해당하는 값이 knowledge에 없다면, 해당 키와 소괄호 쌍을 물음표 ?로 치환해야 합니다. 중첩된 괄호는 존재하지 않으며, 각 키는 knowledge에 최대 한 번 나타납니다.

입력:

• s: 소괄호와 문자열로 이루어진 입력 문자열
• knowledge: [key, value] 형태의 문자열 배열

출력:

• s에서 괄호 안의 키가 knowledge에 따라 적절한 값 또는 ?로 치환된 결과 문자열

접근 방법

이 문제는 문자열 내에서 특정 패턴(괄호로 둘러싸인 키)을 찾고, 그 패턴을 다른 문자열로 대체하는 문제입니다. knowledge 정보를 효율적으로 검색하기 위해 해시 테이블(딕셔너리)을 사용하는 것이 효과적입니다.

1. knowledge 정보 저장: knowledge 배열을 순회하며 키-값 쌍을 해시 테이블에 저장합니다. 이렇게 하면 각 키에 대한 값을 O(1)의 평균 시간 복잡도로 빠르게 찾을 수 있습니다.
2. 문자열 s 파싱 및 처리: 문자열 s를 순회하면서 괄호와 일반 문자열 부분을 구분합니다.
   • 괄호 안의 키를 추출합니다.
   • 추출한 키를 해시 테이블에서 찾아 해당하는 값을 가져옵니다.
   • 값이 있으면 해당 값으로, 없으면 ?로 대체합니다.
   • 괄호 바깥의 일반 문자열 부분은 그대로 유지합니다.

이 접근 방식은 knowledge의 검색 효율성과 문자열 s의 순차적인 처리라는 두 가지 요구사항을 모두 만족시킵니다.

구현 설명

주어진 코드는 다음과 같은 단계를 통해 문제를 해결합니다.

1. knowledge를 해시 테이블(딕셔너리)로 변환

• knowledge 배열을 순회하며 각 [key, value] 쌍을 dict 자료구조에 저장합니다. 여기서 키는 knowledge의 key가 되고, 값은 knowledge의 value가 됩니다. 이렇게 하면 특정 키에 해당하는 값을 O(1) 평균 시간 복잡도로 빠르게 찾을 수 있습니다.

2. 입력 문자열 s를 파싱하여 괄호 안의 키와 일반 문자열 분리

• s를 순회하며 문자들을 words라는 리스트에 저장합니다.
• ( 문자를 만나면, 현재까지 모은 일반 문자들을 word로 합쳐 words 리스트에 추가하고, 괄호 안의 키를 기록하기 위한 start 플래그를 True로 설정합니다.
• start가 True일 때 ) 문자를 만나면, 괄호 안의 문자들을 word로 합치고, 이 word가 키가 됩니다. 이 키와 해당 키가 words 리스트에서 몇 번째 인덱스에 해당하는지를 idx_map 딕셔너리에 저장합니다. words 리스트에는 빈 문자열 ""을 추가하여 괄호 부분이 채워질 자리임을 표시합니다.
• 일반 문자들은 word 리스트에 추가됩니다.
• 문자열의 끝에 도달했을 때 word에 내용이 있다면, 마지막 일반 문자열로 간주하여 words에 추가합니다.

3. 괄호 안의 키를 knowledge 값으로 치환

• knowledge 딕셔너리를 순회합니다.
• 만약 knowledge의 키가 idx_map에 존재한다면, 해당 키가 나오는 모든 words 리스트의 인덱스를 가져옵니다.
• 가져온 인덱스들에 해당하는 words 리스트의 요소를 knowledge의 값으로 변경합니다.

4. 값이 없는 괄호 부분을 ?로 치환하고 결과 문자열 생성

• words 리스트를 다시 순회하며, 여전히 빈 문자열 ""으로 남아있는 요소들(즉, knowledge에서 값을 찾지 못한 괄호 부분)을 ?로 변경합니다.
• 마지막으로 words 리스트의 모든 요소들을 join하여 최종 결과 문자열을 만듭니다.

⏱복잡도 분석

• 시간 복잡도:

  • knowledge를 해시 테이블로 변환하는 데 O(K) 시간이 걸립니다. 여기서 K는 knowledge 배열의 길이입니다.
  • 문자열 s를 순회하며 파싱하는 데 O(N) 시간이 걸립니다. 여기서 N은 s의 길이입니다.
  • knowledge를 순회하며 words 리스트를 업데이트하는 데, 최악의 경우 각 키가 s에 여러 번 나타날 수 있으므로 O(K * M)이 될 수 있습니다. 여기서 M은 s에서 키가 나타나는 최대 횟수입니다. 하지만 각 키는 knowledge에 고유하며, s에서 키가 나오는 횟수는 s의 길이에 비례하므로, 전체적으로는 O(N)으로 볼 수 있습니다.
  • 결과 문자열을 생성하는 데 O(N) 시간이 걸립니다.
  • 따라서 전체 시간 복잡도는 O(N + K) 입니다.

• 공간 복잡도:

  • knowledge를 저장하는 해시 테이블은 O(K)의 공간을 사용합니다.
  • words 리스트는 s를 파싱한 결과를 저장하며, 최대 O(N)의 공간을 사용합니다.
  • idx_map은 키와 해당 인덱스를 저장하며, 최악의 경우 O(N)의 공간을 사용할 수 있습니다.
  • 따라서 전체 공간 복잡도는 O(N + K) 입니다.

핵심 포인트

1. knowledge 정보의 효율적인 검색: knowledge 배열을 해시 테이블(파이썬의 딕셔너리)로 변환하여 각 키에 대한 값을 O(1) 평균 시간 복잡도로 빠르게 조회할 수 있도록 합니다.
2. 문자열 s의 순차적 파싱: 문자열 s를 순회하면서 괄호 (와 )를 기준으로 키를 추출하고, 일반 문자열 부분을 구분하는 로직이 중요합니다. 중첩 괄호가 없으므로 스택 없이 간단한 플래그(start)를 사용하여 처리할 수 있습니다.
3. 결과 빌딩 전략: 파싱된 문자열 조각들(일반 문자열, 대체될 값 또는 ?)을 리스트에 저장한 후, 마지막에 모두 합치는 방식은 문자열 변경의 효율성을 높여줍니다. 직접 문자열을 변경하면 비효율적일 수 있습니다.

풀이 코드

class Solution:
    def evaluate(self, s: str, knowledge: list[list[str]]) -> str:
        l = len(s)
        words = []
        idx_map = {}
        idx = 0
        start = False
        word = []
        for i in range(l):
            if s[i] == "(":
                if word:
                    w = "".join(word)
                    words.append(w)
                    idx += 1

                word = []
                start = True

            elif start and s[i] == ")":
                if word:
                    w = "".join(word)
                    if w in idx_map:
                        idx_map[w].append(idx)
                    else:
                        idx_map[w] = [idx]
                    idx += 1
                    words.append("")
                
                word = []
                start = False

            else:
                word.append(s[i])
        if word:
            w = "".join(word)
            words.append(w)
        
        for x,y in knowledge:
            if x in idx_map:
                for i in idx_map[x]:
                    words[i] = y

        for i in range(len(words)):
            if not words[i]:
                words[i] = "?"

        return "".join(words)