Run Code
|
API
|
Code Wall
|
Users
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Blog
Num ways to decode a string -Facebook interview
//'main' method must be in a class 'Rextester'. //Compiler version 1.8.0_111 import java.util.*; import java.lang.*; class Rextester { /*Find number of ways given data can be decoded * where a=1, b=2,...z=26. if data = "123" answer = 3 ("abc","lc","aw") */ public static int numWays(String data){ int[] memo = new int[data.length()+1]; for(int i=0;i<memo.length;i++){ memo[i] = -1; } return helper(data,data.length(),memo); } public static int helper(String data, int k, int[] memo){ int result; //System.out.println("calling k="+k+" data="+data); if(k==0) return 1; //System.out.println("data.charAt(data.length()-k)="+data.charAt(data.length()-k)); if(data.charAt(data.length()-k)=='0') return 0; //System.out.println("memo[k]="+memo[k]); if(memo[k]!=-1) return memo[k]; result = helper(data,k-1,memo); //check additional conditions if( k>=2 && (Integer.parseInt(data.substring(data.length()-k,data.length()-k+2))<27)){ result += helper(data,k-2,memo); } memo[k] = result; return result; } public static void main(String args[]) { System.out.println("Hello, World!"); System.out.println(numWays("1234")); } }
run
|
edit
|
history
|
help
0
Please
log in
to post a comment.
1 to 100 except 30 to40
Print Count Strings
ArrayOperation
Simple imitation for show banners on priorities
fizzbuzz
Binary Tree Max path Sum
DevStuff
Minimum Vertices to Traverse Directed Graph
Bank System
Feet-inches input validation
Please log in to post a comment.