[Python] 1309. Decrypt String from Alphabet to Integer Mapping

Decrypt String from Alphabet to Integer Mapping - LeetCode

 

문제 설명

You are given a string s formed by digits and '#'. We want to map s to English lowercase characters as follows:

• Characters ('a' to 'i') are represented by ('1' to '9') respectively.
• Characters ('j' to 'z') are represented by ('10#' to '26#') respectively.

Return the string formed after mapping.

The test cases are generated so that a unique mapping will always exist.

 

Example 1:

Input: s = "10#11#12"
Output: "jkab"
Explanation: "j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".

 

Example 2:

Input: s = "1326#"
Output: "acz"

 

 

문제 풀이

(1) 사용한 알고리즘

완전탐색

 

(2) 시간복잡도

O(n)

 

(3) 설명

'#' 앞의 두 숫자는 항상 하나의 알파벳으로 변환되고, 그 외에는 하나의 숫자만 알파벳으로 변환된다는 규칙이 있다.

따라서 s를 완전탐색하면서

• 현재 인덱스 + 2의 문자가 '#'인 경우, 현재 인덱스부터 시작하는 두 숫자를 알파벳으로 변환한다.
• 현재 인덱스 + 2의 문자가 '#'이 아닐 경우, 현재 인덱스의 한 숫자를 알파벳으로 변환한다.

 

(4) 풀이 코드

class Solution:
    def freqAlphabets(self, s: str) -> str:
        temp = []
        i = 0
        while i < len(s):
            if (i + 2) < len(s) and s[i + 2] == '#':
                temp.append(chr(int(s[i : i+2]) + ord('a') - 1))
                i += 3
            else:
                temp.append(chr(int(s[i]) + ord('a') - 1))
                i += 1

        return "".join(temp)