Title: Decode Ways Source: leetcode.com
A message containing letters from A-Z is being encoded to numbers using the following mapping:
|
1 2 3 4 |
'A' -> 1 'B' -> 2 ... 'Z' -> 26 |
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12",
could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
/* https://leetcode.com/problems/decode-ways/ */ import java.util.ArrayList; import java.util.List; class DecodeWays { public int numDecodings(String s) { if(s==null || s.equals("")) return 0; List<ArrayList<String>> list = new ArrayList<>(); helper(s, list, new ArrayList<String>()); return list.size(); } public void helper(String s, List<ArrayList<String>> list, ArrayList<String> a) { if(s.length()==0) { System.out.println(a); list.add(new ArrayList<String>(a)); a = new ArrayList<>(); return; } if(s.length()>0) { a.add(s.substring(0, 1)); helper(s.substring(1), list, a); } if(s.length()>=2) { String temp = s.substring(0, 2); if(Integer.parseInt(temp)<27) { a.add(temp); helper(s.substring(2), list, a); } } } public static void main(String args[]) { DecodeWays d = new DecodeWays(); System.out.println(d.numDecodings("6065812287883668764831544958683283296479682877898293612168136334983851946827579555449329483852397155")); } } |
Bloody aweful..!
Will give wrong answer when input is “0”.