[Dart] 205. Isomorphic Strings

1. 문제

https://leetcode.com/problems/isomorphic-strings/description/?envType=study-plan-v2&envId=top-interview-150

 

 

2. 요구 사항

1) 두 개의 문자열 s와 t가 주어졌을 때 두 문자열이 동형인지 판별한다.

2) 동형 문자열은 s 문자열의 문자 하나가 t 문자열의 문자로 일대일 매핑 되는 것이다.

3) 같은 문자는 같은 문자로 매핑되어야 하며, 다른 문자로 바뀌어서는 안된다.

 

 

3. 핵심 아이디어

 

1) 각 문자를 ASCII 값으로 대체 후 비교

 

각 문자열의 문자를 정수(ASCII) 값으로 변환하여,

두 개의 List<int> 배열을 만들어 각 문자의 최근 등장 위치를 저장한다.

 

문자가 이전에 등장한 위치가 서로 다르면, 1대1 매핑이 되지 않은 것이므로 false를 반환한다.

 

반복문을 모두 통과하면 두 문자열은 동형 관계이므로 true를 반환한다.

 

 

 

 

2) 코드

class Solution {
  bool isIsomorphic(String s, String t) {

    // ASCII 문자 기준으로 각 문자의 최근 등장 위치를 저장할 배열 (128은 ASCII 문자 개수)
    List<int> mapS = List.filled(128, -1);  // s의 문자 대응
    List<int> mapT = List.filled(128, -1);  // t의 문자 대응

    for (int i = 0; i < s.length; i++) {
      // 현재 문자를 정수(ASCII)로 변환
      int charS = s.codeUnitAt(i);
      int charT = t.codeUnitAt(i);

      // 두 문자열의 현재 문자의 이전 등장 위치가 다르면 false
      if (mapS[charS] != mapT[charT]) return false;

      // 현재 문자의 등장 위치를 기록
      mapS[charS] = i;
      mapT[charT] = i;
    }

    return true;
  }
}

 

- 시간 복잡도 : O(n)

- 공간 복잡도 : O(1)