算法的学习笔记—把数字翻译成字符串

😀前言
在日常生活中，我们经常会遇到各种编码和解码的问题。今天，我们将讨论一个有趣的问题：如何将一串数字翻译成字母，并计算出有多少种不同的翻译方法。

🏠个人主页：尘觉主页

💝把数字翻译成字符串

Leetcode

💞问题描述

给定一个由数字组成的字符串，我们需要按照以下规则将其翻译成字母：

• 数字1-26分别对应字母a-z，例如1对应a，2对应b，…，26对应z。
• 例如，对于输入“12258”，它可以被翻译为以下几种不同的字符串：
  • “abbeh”
  • “lbeh”
  • “aveh”
  • “abyh”
  • “lyh”

总共有5种不同的翻译方式。我们的任务是实现一个函数来计算一个数字字符串有多少种不同的翻译方法。

❤️‍🔥解题思路

要解决这个问题，我们可以使用动态规划（Dynamic Programming）的方法。动态规划是一种将问题分解成更小的子问题并逐步解决的技术。在这个问题中，我们可以逐步计算每个子字符串的解码方式。

步骤

1. 初始化动态规划数组：我们使用一个数组 dp 来记录每个位置的翻译方法数。dp[i] 表示字符串前 i 个字符的翻译方法数。
2. 处理边界情况：首先，如果字符串为空或首字符为’0’，则没有合法的翻译方法。
3. 状态转移方程：
   • 如果当前位置的一个数字可以独立翻译（即不为’0’），则该位置的翻译方法数应加上前一位置的翻译方法数，即 dp[i] += dp[i - 1]。
   • 如果当前位置的两个数字组合在一起可以翻译（即其值在10到26之间），则该位置的翻译方法数应加上前两位置的翻译方法数，即 dp[i] += dp[i - 2]。
4. 返回结果：最终，dp[n]（n为字符串的长度）就是我们需要的结果。

🥰代码实现

以下是具体的代码实现：

public int numDecodings(String s) {// 如果字符串为空或以'0'开头，则没有合法的翻译方法if (s == null || s.length() == 0) {return 0;}int n = s.length();int[] dp = new int[n + 1];// 初始化，空字符串有一种翻译方式dp[0] = 1;// 如果字符串的第一个字符不为'0'，则有一种翻译方式dp[1] = s.charAt(0) == '0' ? 0 : 1;// 动态规划求解for (int i = 2; i <= n; i++) {// 处理单个数字的翻译int one = Integer.valueOf(s.substring(i - 1, i));if (one != 0) {dp[i] += dp[i - 1];}// 处理两个数字组合的翻译if (s.charAt(i - 2) != '0') {int two = Integer.valueOf(s.substring(i - 2, i));if (two <= 26) {dp[i] += dp[i - 2];}}}// 返回最后的结果return dp[n];
}

代码解析

• 初始化部分：dp[0] 初始化为1，表示空字符串有一种翻译方式。dp[1] 根据字符串的第一个字符是否为’0’来确定是否有合法的翻译方式。
• 主循环：从第二个字符开始，每次计算一个字符和两个字符的翻译可能性，并累加到 dp[i] 中。
• 时间复杂度：该算法的时间复杂度为O(n)，其中n为字符串的长度。

😄总结

通过动态规划的方法，我们可以高效地计算出一个数字字符串有多少种不同的翻译方法。这个问题不仅考察了我们对动态规划的理解，还让我们熟悉了如何处理字符串中的边界情况和状态转移。希望通过这个例子的讲解，能够帮助你更好地理解动态规划的应用。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞