2301. Match Substring After Replacement / TypeScript

You are given two strings s and sub. You are also given a 2D character array mappings where mappings[i] = [oldi, newi] indicates that you may perform the following operation any number of times:

• Replace a character oldi of sub with newi.

Each character in sub cannot be replaced more than once.

Return true if it is possible to make sub a substring of s by replacing zero or more characters according to mappings. Otherwise, return false.

A substring is a contiguous non-empty sequence of characters within a string.

 

Example 1:

Input: s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]
Output: true
Explanation: Replace the first 'e' in sub with '3' and 't' in sub with '7'.
Now sub = "l3e7" is a substring of s, so we return true.

Example 2:

Input: s = "fooleetbar", sub = "f00l", mappings = [["o","0"]]
Output: false
Explanation: The string "f00l" is not a substring of s and no replacements can be made.
Note that we cannot replace '0' with 'o'.

Example 3:

Input: s = "Fool33tbaR", sub = "leetd", mappings = [["e","3"],["t","7"],["t","8"],["d","b"],["p","b"]]
Output: true
Explanation: Replace the first and second 'e' in sub with '3' and 'd' in sub with 'b'.
Now sub = "l33tb" is a substring of s, so we return true.

 

출처 : https://leetcode.com/problems/match-substring-after-replacement/description/

 

 

풀이

function matchString(s: string, sub: string, idx: number, map: Record<any, any>): boolean {
  for(let i = 0; i < sub.length; i++) {
    if(s[idx + i] === sub[i]) continue;
    if(map[s[idx + i]] && map[s[idx + i]][sub[i]]) continue;
    return false;
  }
  return true;
}

function matchReplacement(s: string, sub: string, mappings: string[][]): boolean {
  const map = {};
  for (let i = 0; i < mappings.length; i++) {
    const values = mappings[i];
    map[values[1]] === undefined
      ? map[values[1]] = { [values[0]]: true }
      : map[values[1]][values[0]] = true;
  }

  for(let i = 0; i < s.length; i++) {
    if(matchString(s, sub, i, map)) return true;
  }
  return false;
};

 

 

문자열이 주어졌을 때, 특정 부분 문자열과 매칭되는지 확인하는 기능을 수행

 

1. matchString 함수

matchString 함수는 주어진 문자열 s에서 시작 위치 idx부터 부분 문자열 sub이 일치하는지 검사.

이때, 특정 문자 쌍의 변환 규칙이 map에 존재할 경우, 해당 규칙을 따름

매개변수

• s: string: 원본 문자열
• sub: string: 비교할 부분 문자열
• idx: number: 원본 문자열에서 비교를 시작할 위치
• map: Record<any, any>: 특정 문자쌍의 변환 규칙을 담고 있는 맵

동작

1. sub 문자열의 각 문자를 순차적으로 확인
2. 원본 문자열 s의 현재 위치의 문자(s[idx + i])가 sub[i] 문자와 같으면 계속 진행
3. 만약 다르다면, map에 해당 문자 쌍이 있는지 확인. 변환 규칙에 따라 변환 가능한 경우에도 매칭이 성립
4. 매칭이 불가능하면 false를 반환하고, 끝까지 매칭되면 true를 반환

2. matchReplacement 함수

이 함수는 주어진 문자열 s에 대해 특정 부분 문자열 sub이 존재하는지, 그리고 주어진 문자 변환 규칙(mappings)을 적용했을 때도 매칭이 가능한지를 확인

매개변수

• s: string: 원본 문자열
• sub: string: 비교할 부분 문자열
• mappings: string[][]: 변환 규칙을 담은 2차원 배열. 각 배열의 원소는 변환 가능한 문자 쌍을 나타냄

동작

1. 변환 규칙을 map 객체로 변환. 여기서 각 쌍의 첫 번째 값은 변환할 수 있는 대상 문자이고, 두 번째 값은 변환된 문자
2. 원본 문자열 s를 처음부터 끝까지 순차적으로 탐색하면서 sub이 해당 위치에서 시작하는지 확인.
3. matchString 함수를 사용하여 해당 위치에서 변환 규칙을 고려한 매칭이 가능한지 판단.
4. 매칭이 성공하면 true를 반환하고, 그렇지 않으면 끝까지 탐색한 후 false를 반환

 

예시 s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]

 

1. matchReplacement 함수 실행

1.1. map 객체 생성

mappings 배열을 사용하여 변환 규칙을 map 객체로 변환

이 과정에서, 각 변환 규칙의 두 번째 문자를 키(key)로, 첫 번째 문자를 값(value)으로 저장

 

 for (let i = 0; i < mappings.length; i++) {
    const values = mappings[i];
    map[values[1]] === undefined
      ? map[values[1]] = { [values[0]]: true }
      : map[values[1]][values[0]] = true;
  }

 

 

• 이 루프는 mappings 배열을 순회하면서 각 매핑 쌍(values)을 가져옴.
• mappings[i]는 한 쌍의 배열. 예를 들어, mappings[i] = ["e", "3"]이면, values[0]는 "e"이고, values[1]는 "3"
• values[0]은 변환할 수 있는 원래 문자이고, values[1]은 대체 문자

 

map[values[1]] === undefined
  ? map[values[1]] = { [values[0]]: true }
  : map[values[1]][values[0]] = true;

 

이 부분은 변환 규칙을 map에 저장하는 방식.

map은 다음과 같은 구조

• values[1] (두 번째 값, 대체 문자)를 키로 사용하여, 그 값이 객체 형태로 변환
• 이 객체는 values[0] (첫 번째 값, 원래 문자)를 키로 사용하여 true 값을 저장.
• 이는 대체 문자가 원래 문자로 변환될 수 있다는 것을 의미

map[values[1]] === undefined

• 만약 map[values[1]]가 존재하지 않는다면, 즉 map에 values[1] 키가 없다면 새로운 객체를 생성
  • map[values[1]] = { [values[0]]: true }: values[1]을 키로 하고, 그 값으로 { [values[0]]: true }라는 객체를 할당.
    • 예: map["3"] = { "e": true } → 이는 "3"이 "e"로 변환될 수 있다는 것을 나타냄

 

반대로, 만약 map[values[1]]가 이미 존재한다면, 해당 객체에 새로운 변환 규칙을 추가.

• map[values[1]][values[0]] = true로 추가 변환 규칙을 기록
• 예: 이미 map["t"] = { "7": true }가 존재할 경우, 추가로 map["t"]["8"] = true를 추가

 

 

map = {
  "3": { "e": true },
  "7": { "t": true },
  "8": { "t": true }
}

 

1.2. matchString 호출을 위한 루프

이제 s 문자열을 처음부터 끝까지 탐색하면서, sub 문자열이 s에서 일치하는 부분이 있는지 확인

• s = "fool3e7bar"는 길이가 10이므로, 인덱스 0부터 9까지 반복
• (i = 0부터 i = s.length - sub.length = 6까지 반복합니다.)

각 인덱스에서 matchString 함수를 호출하여, s의 특정 위치에서 sub과 매칭이 가능한지를 확인

 

 

2. matchString 함수 실행

2.1. 첫 번째 호출: i = 0

• s = "fool3e7bar"에서 sub = "leet"를 찾기 위해 idx = 0에서 비교를 시작

1. 첫 번째 문자:
   • s[0] = "f", sub[0] = "l"
   • f와 l이 다르므로 바로 false를 반환
   • 결과: matchString("fool3e7bar", "leet", 0, map) → false

2.2. 두 번째 호출: i = 1

• s = "fool3e7bar"에서 idx = 1에서 비교를 시작

1. 첫 번째 문자:
   • s[1] = "o", sub[0] = "l"
   • o와 l이 다르므로 false를 반환
   • 결과: matchString("fool3e7bar", "leet", 1, map) → false

2.3. 세 번째 호출: i = 2

• s = "fool3e7bar"에서 idx = 2에서 비교를 시작

1. 첫 번째 문자:
   • s[2] = "o", sub[0] = "l"
   • o와 l이 다르므로 false를 반환
   • 결과: matchString("fool3e7bar", "leet", 2, map) → false

2.4. 네 번째 호출: i = 3

• s = "fool3e7bar"에서 idx = 3에서 비교를 시작

1. 첫 번째 문자:
   • s[3] = "l", sub[0] = "l"
   • 일치하므로 다음 문자로 진행
2. 두 번째 문자:
   • s[4] = "3", sub[1] = "e"
   • 3와 e는 다르지만, map에 3 → e 변환 규칙이 있으므로 매칭이 성립, 다음 문자로 진행
3. 세 번째 문자:
   • s[5] = "e", sub[2] = "e"
   • 일치하므로 다음 문자로 진행
4. 네 번째 문자:
   • s[6] = "7", sub[3] = "t"
   • 7과 t는 다르지만, map에 7 → t 변환 규칙이 있으므로 매칭이 성립

모든 문자가 매칭되었으므로, true를 반환

결과: matchString("fool3e7bar", "leet", 3, map) → true

3. 최종 결과

matchString 함수가 true를 반환했으므로, matchReplacement 함수도 true를 반환