LeetCode - 3335. Total Characters in String After Transformations I

문제링크

 

문제 설명

문자열 s와 정수 t가 주어집니다. 여기서 t는 총 변환 횟수를 나타냅니다.

한 번의 변환(Transformation)에서 문자열 s의 모든 문자는 다음 규칙에 따라 변경됩니다:

• 문자가 'z'인 경우 → 'ab'로 확장
• 문자가 'z'가 아닌 경우 → 알파벳 상 다음 문자로 변경
  • 예: 'a' → 'b', 'b' → 'c', ..., 'y' → 'z'

정확히 t번의 변환을 수행한 뒤의 문자열 길이를 구하세요.
결과가 매우 클 수 있으므로, 정답을 10^9+7 로 나눈 값을 반환하세요.

제한 사항

• 1 <= s.length <= 10^5
• s consists only of lowercase English letters.
• 1 <= t <= 10^5

예시

Example 1:

Input: s = "abcyy", t = 2

Output: 7

Explanation:

• First Transformation (t = 1):
  • 'a' becomes 'b'
  • 'b' becomes 'c'
  • 'c' becomes 'd'
  • 'y' becomes 'z'
  • 'y' becomes 'z'
  • String after the first transformation: "bcdzz"
• Second Transformation (t = 2):
  • 'b' becomes 'c'
  • 'c' becomes 'd'
  • 'd' becomes 'e'
  • 'z' becomes "ab"
  • 'z' becomes "ab"
  • String after the second transformation: "cdeabab"
• Final Length of the string: The string is "cdeabab", which has 7 characters.

Example 2:

Input: s = "azbk", t = 1

Output: 5

Explanation:

• First Transformation (t = 1):
  • 'a' becomes 'b'
  • 'z' becomes "ab"
  • 'b' becomes 'c'
  • 'k' becomes 'l'
  • String after the first transformation: "babcl"
• Final Length of the string: The string is "babcl", which has 5 characters.

풀이 흐름

• 처음에 든 생각은 s의 각 알파벳별로 t만큼 변환을 했을 때의 길이를 합산해주면 되겠다고 판단했습니다.
• 처음에는 간단하게 알파벳 - 'a' + t를 해서 나온 값을 수학적 연산을 통해 O(1)만에 구할 수 있겠다고 판단했지만 'z' -> 'ab'로 변하기 때문에 각 자리 별로 계산해야되는 방식이 달라져 쉽게 계산식을 만들 수 없었습니다.
• f(c, t)라는 함수를 c라는 알파벳이 t만큼 변환됐을 때의 길이를 반환하는 함수라고 정의했습니다.
• 그러면 f(c, t)는 f(c + 1, t - 1)이 됩니다.
  • 예를 들어 'b'를 5만큼 변환하는 것은 'c'를 4만큼 변환한 결과와 같기 때문입니다.
• 예외는 c가 'z'일 때입니다. 'z'면 'ab'로 바뀌기 때문에 'z'를 t만큼 변환한 값은 'a'를 t - 1만큼 변환한 값과 'b'를 t - 1만큼 변환한 값의 합과 같습니다.

코드

class Solution {
    int[][] dp;
    int mod = 1000000007;
    int T;
    public int lengthAfterTransformations(String s, int t) {
        dp = new int[26][t + 1];
        int count = 0;
        T = t;
        for (int i = 0; i < s.length(); i++) {
            count = (count + f(s.charAt(i) - 'a', 0) % mod) % mod;
        }
        return count;
    }

    private int f(int c, int t) {
        if (t >= T) return 1;
        if (dp[c][t] != 0) return dp[c][t] % mod;
        if (c == 25) {
            dp[c][t] = (f(0, t + 1) + f(1, t + 1)) % mod;
        } else {
            dp[c][t] = f(c + 1, t + 1) % mod;
        }
        return dp[c][t] % mod;
    }
}