题目链接:https://leetcode-cn.com/problems/decode-ways/description/
参考:https://www.jianshu.com/p/5a604070cd11
题目大意:将一串数字,编码成A-Z的字符串。因为12-->L,或者12-->AB。所有12转成字符串一共有两种方式。该题目是求一共有多少种方案,所以可以使用dp方法。如果是求具体方案,则需要使用dfs。
状态转移方程:
(1) dp[0] = 0 (2) dp[1] = 1, if str[1] is valid dp[1] = 0, if str[1] is not valid (3)
dp[n] = 0
if str[n] is valid
dp[n] += dp[n - 1] if str[n - 1] combine str[n] is valid dp[n] += (i - 2 == 0) ? 1 : dp[n - 2]
dp[i]:前面i个字符串可以转义成多少种密文。
public int numDecodings(String s) { if (s.length() == 0 || s == null || s == "0") return 0; int[] dp = new int[s.length() + 1]; dp[0] = 1; if (isValid(s.substring(0, 1))) dp[1] = 1; else dp[1] = 0; for (int i = 2; i <= s.length(); i++) { if (isValid(s.substring(i - 1, i))) dp[i]= dp[i - 1]; if (isValid(s.substring(i - 2, i))) dp[i]= dp[i - 2]+dp[i]; } return dp[s.length()]; } public boolean isValid(String s) { if (s.charAt(0) == '0') return false; int code = Integer.parseInt(s); return code >= 1 && code <= 26; }
扩展一下:如果不需要时间限制,并且需要求出具体方案。则需要使用dfs算法求出具体方案。
注意:Java中的substring(beginIndex,endIndex):大概意思返回 [beginIndex,endIndex)区间的值。所以endIndex的最大值可以是字符串的程度。
Returns a new string that is a substring of this string. The substring begins at the specified beginIndex
and extends to the character at index endIndex - 1
. Thus the length of the substring is endIndex-beginIndex
.
Examples:
"hamburger".substring(4, 8) returns "urge" "smiles".substring(1, 5) returns "mile"
System.out.println("226".substring(3, 3));//返回为""(空)
接下来使用dfs计算出所有的可能的方式。
import java.util.HashMap; import java.util.LinkedList; import java.util.Map; public class Solution { static LinkedList<String> list = new LinkedList<String>(); static LinkedList<LinkedList<String>> ans = new LinkedList<LinkedList<String>>(); Map<String, String> map = new HashMap<String, String>(); public int numDecodings(String s) { ans.clear(); char[] alphatableb = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' }; for (int i = 0; i < alphatableb.length; i++) { map.put(i + 1 + "", alphatableb[i] + ""); } dfs(s); return ans.size(); } private void dfs(String s) { if (s.isEmpty() || s.length() == 0) { LinkedList<String> tmp = new LinkedList<String>(); tmp.addAll(list); ans.add(tmp); return; } for (int i = 1; i <= 2&&i<=s.length(); i++) { String str = s.substring(0, i); if (isValid(str)) { String ss = map.get(str); list.add(ss); dfs(s.substring(i, s.length())); list.pollLast(); } else { return; } } } public boolean isValid(String s) { if (s.charAt(0) == '0') return false; int code = Integer.parseInt(s); return code >= 1 && code <= 26; } public static void main(String[] args) { System.out.println("226".substring(3, 3)); int len = new Solution().numDecodings("226"); System.out.println(len); System.out.println(ans); } }