639. Decode Ways II

leetcode hard

#array#csharp#dynamic-programming#hard#leetcode#string

Task

Сообщение, содержащее буквы от A-Z, может быть закодировано в цифры с помощью следующего отображения: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" Чтобы декодировать закодированное сообщение, все цифры должны быть сгруппированы, а затем снова преобразованы в буквы с помощью обратного отображения (может быть несколько способов). Например, "11106" может быть преобразовано в: "AAJF" с группировкой (1 1 10 6) "KJF" с группировкой (11 10 6) Обратите внимание, что группировка (1 11 06) недействительна, поскольку "06" не может быть преобразовано в "F", так как "6" отличается от "06". В дополнение к вышеуказанным преобразованиям кодированное сообщение может содержать символ "*", который может представлять любую цифру от "1" до "9" ("0" исключается). Например, кодированное сообщение "1*" может представлять любое из кодированных сообщений "11", "12", "13", "14", "15", "16", "17", "18" или "19". Декодирование "1*" эквивалентно декодированию любого из кодированных сообщений, которые оно может представлять. Если задана строка s, состоящая из цифр и символов '*', верните количество способов ее декодирования. Поскольку ответ может быть очень большим, верните его по модулю 109 + 7.

Пример:

Input: s = "*"

Output: 9

C# solution

matched/original

using System;
public class Solution {
    public int NumDecodings(string s) {
        const int MOD = 1000000007;
        int n = s.Length;
        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            if (s[i - 1] == '*') {
                dp[i] = 9 * dp[i - 1];
            } else if (s[i - 1] != '0') {
                dp[i] = dp[i - 1];
            }
            if (i > 1) {
                if (s[i - 2] == '*') {
                    if (s[i - 1] == '*') {
                        dp[i] += 15 * dp[i - 2];
                    } else if (s[i - 1] <= '6') {
                        dp[i] += 2 * dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2];
                    }
                } else if (s[i - 2] == '1') {
                    if (s[i - 1] == '*') {
                        dp[i] += 9 * dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2];
                    }
                } else if (s[i - 2] == '2') {
                    if (s[i - 1] == '*') {
                        dp[i] += 6 * dp[i - 2];
                    } else if (s[i - 1] <= '6') {
                        dp[i] += dp[i - 2];
                    }
                }
            }
            dp[i] %= MOD;
        }
        return (int)dp[n];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NumDecodings(string s) {
        const int MOD = 1000000007;
        int n = s.size();
        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            if (s[i - 1] == '*') {
                dp[i] = 9 * dp[i - 1];
            } else if (s[i - 1] != '0') {
                dp[i] = dp[i - 1];
            }
            if (i > 1) {
                if (s[i - 2] == '*') {
                    if (s[i - 1] == '*') {
                        dp[i] += 15 * dp[i - 2];
                    } else if (s[i - 1] <= '6') {
                        dp[i] += 2 * dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2];
                    }
                } else if (s[i - 2] == '1') {
                    if (s[i - 1] == '*') {
                        dp[i] += 9 * dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2];
                    }
                } else if (s[i - 2] == '2') {
                    if (s[i - 1] == '*') {
                        dp[i] += 6 * dp[i - 2];
                    } else if (s[i - 1] <= '6') {
                        dp[i] += dp[i - 2];
                    }
                }
            }
            dp[i] %= MOD;
        }
        return (int)dp[n];
    }
}

Java solution

matched/original

public class Solution {
    public int numDecodings(String s) {
        final int MOD = 1000000007;
        int n = s.length();
        long[] dp = new long[n + 1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            if (s.charAt(i - 1) == '*') {
                dp[i] = 9 * dp[i - 1];
            } else if (s.charAt(i - 1) != '0') {
                dp[i] = dp[i - 1];
            }

            if (i > 1) {
                if (s.charAt(i - 2) == '*') {
                    if (s.charAt(i - 1) == '*') {
                        dp[i] += 15 * dp[i - 2];
                    } else if (s.charAt(i - 1) <= '6') {
                        dp[i] += 2 * dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2];
                    }
                } else if (s.charAt(i - 2) == '1') {
                    if (s.charAt(i - 1) == '*') {
                        dp[i] += 9 * dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2];
                    }
                } else if (s.charAt(i - 2) == '2') {
                    if (s.charAt(i - 1) == '*') {
                        dp[i] += 6 * dp[i - 2];
                    } else if (s.charAt(i - 1) <= '6') {
                        dp[i] += dp[i - 2];
                    }
                }
            }

            dp[i] %= MOD;
        }

        return (int) dp[n];
    }
}

JavaScript solution

matched/original

var numDecodings = function(s) {
    const MOD = 1e9 + 7;
    const n = s.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;

    for (let i = 1; i <= n; i++) {
        if (s[i - 1] === '*') {
            dp[i] = 9 * dp[i - 1];
        } else if (s[i - 1] !== '0') {
            dp[i] = dp[i - 1];
        }

        if (i > 1) {
            if (s[i - 2] === '*') {
                if (s[i - 1] === '*') {
                    dp[i] += 15 * dp[i - 2];
                } else if ('0' <= s[i - 1] && s[i - 1] <= '6') {
                    dp[i] += 2 * dp[i - 2];
                } else {
                    dp[i] += dp[i - 2];
                }
            } else if (s[i - 2] === '1') {
                if (s[i - 1] === '*') {
                    dp[i] += 9 * dp[i - 2];
                } else {
                    dp[i] += dp[i - 2];
                }
            } else if (s[i - 2] === '2') {
                if (s[i - 1] === '*') {
                    dp[i] += 6 * dp[i - 2];
                } else if ('0' <= s[i - 1] && s[i - 1] <= '6') {
                    dp[i] += dp[i - 2];
                }
            }
        }

        dp[i] %= MOD;
    }

    return dp[n];
};

Python solution

matched/original

def numDecodings(s: str) -> int:
    MOD = 10**9 + 7
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1

    for i in range(1, n + 1):
        if s[i - 1] == '*':
            dp[i] += 9 * dp[i - 1]
        elif s[i - 1] != '0':
            dp[i] += dp[i - 1]

        if i > 1:
            if s[i - 2] == '*':
                if s[i - 1] == '*':
                    dp[i] += 15 * dp[i - 2]
                elif '0' <= s[i - 1] <= '6':
                    dp[i] += 2 * dp[i - 2]
                else:
                    dp[i] += dp[i - 2]
            elif s[i - 2] == '1':
                if s[i - 1] == '*':
                    dp[i] += 9 * dp[i - 2]
                else:
                    dp[i] += dp[i - 2]
            elif s[i - 2] == '2':
                if s[i - 1] == '*':
                    dp[i] += 6 * dp[i - 2]
                elif '0' <= s[i - 1] <= '6':
                    dp[i] += dp[i - 2]

        dp[i] %= MOD

    return dp[n]

Go solution

matched/original

package main

import (
  "fmt"
)

func numDecodings(s string) int {
  const MOD = 1000000007
  n := len(s)
  dp := make([]int, n+1)
  dp[0] = 1

  for i := 1; i <= n; i++ {
    if s[i-1] == '*' {
      dp[i] = 9 * dp[i-1]
    } else if s[i-1] != '0' {
      dp[i] = dp[i-1]
    }

    if i > 1 {
      if s[i-2] == '*' {
        if s[i-1] == '*' {
          dp[i] += 15 * dp[i-2]
        } else if s[i-1] >= '0' && s[i-1] <= '6' {
          dp[i] += 2 * dp[i-2]
        } else {
          dp[i] += dp[i-2]
        }
      } else if s[i-2] == '1' {
        if s[i-1] == '*' {
          dp[i] += 9 * dp[i-2]
        } else {
          dp[i] += dp[i-2]
        }
      } else if s[i-2] == '2' {
        if s[i-1] == '*' {
          dp[i] += 6 * dp[i-2]
        } else if s[i-1] >= '0' && s[i-1] <= '6' {
          dp[i] += dp[i-2]
        }
      }
    }

    dp[i] %= MOD
  }

  return dp[n]
}

Explanation

Algorithm

Инициализация

Создайте массив dp, где dp[i] представляет количество способов декодирования подстроки s[0:i]. Установите начальные значения dp[0] = 1 (пустая строка имеет один способ декодирования).

Обход строки

Используйте цикл для обхода строки и вычисления количества способов декодирования для каждого символа, включая обработку символа '*'.

Модульное вычисление

Поскольку количество способов декодирования может быть большим, вычисляйте результаты по модулю 10^9 + 7.

😎