(FB Phone Interview)If a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.


  • 0
    T

    If a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.

    For example:
    Input: "1123". You need to general all valid alphabet codes from this string.

    Output List
    aabc //a = 1, a = 1, b = 2, c = 3
    kbc // since k is 11, b = 2, c= 3
    alc // a = 1, l = 12, c = 3
    aaw // a= 1, a =1, w= 23
    kw // k = 11, w = 23


  • 0
    D

    This problem is Decode Ways:

    public class Solution {
        public int numDecodings(String s) {
            if(s == null || s.length()==0)
                return 0;
            
            int[] dp = new int[s.length()+1];
            
            dp[0] = 1;
            dp[1] = s.charAt(0)=='0'?0:1;
            
            for(int i = 2; i<= s.length(); i++){
                int first = Integer.valueOf(s.substring(i-1,i));
                int second = Integer.valueOf(s.substring(i-2,i));
                
                if(first>=1 && first<=9)
                    dp[i] += dp[i-1];
                if(second>=10 && second<=26)
                    dp[i] += dp[i-2];
            }
            
            return dp[s.length()];
        }
    }
    

  • 0
    D

    @dattasainathd The above code can give you number of ways you can decode string.


  • 1
    S

    A python solution using , Skienna's backtracking template from Algorithm Design Manual :)

    
    def process_solution(a,result):
        dic = dict()
        for i in range(1,27):
            dic[str(i)] = chr(ord('a') + i - 1)
        result.append( ''.join([ dic[x] for x in a ]) )
    
    def construct_candidates(s):
        candidates = []
        candidates.append(s[0])
        if len(s) > 1:
            candidates.append(s[0:2])
        return candidates
    
    def backtrack(a,s,result):
        if len(s) == 0:
            process_solution(a,result)
        else:
            candidates = construct_candidates(s)
            for candidate in candidates:
                a.append(candidate)
                backtrack(a,s[len(candidate):],result)
                a.pop()
    
    
    def get_encodings(s):
        a = []
        result = []
        backtrack(a,s,result)
        return result

  • 0
    S

    @dattasainathd i think the question asks about finding all encodings, not just count of encodings. I trust your solution is to count number of encodings.


  • 0
    T

    Solution is a variation of backtracking to handle the 2 digit cases. I don't believe a 'good' solution exists with non-exponential properties. DP isn't an option because space usage explodes.

    I presume the "Decode Ways" problem is based on counts because that allows for DP based optimization; returning all solutions, as in this problem, does not.

    void decodeWays(vector<string> &res, string &t, string &s, int i)
    {
        if (i == s.size()) {
            res.push_back(t);
            return;
        }
        if (s[i] != '0') {
            t.push_back(s[i] - '1' + 'a');
            decodeWays(res, t, s, i+1);
            t.pop_back();
        }
        if (i < s.size()-1 && s[i] == '1') {
            t.push_back(s[i+1] - '1' + 'a' + 10);
            decodeWays(res, t, s, i+2);
            t.pop_back();
        }
        if (i < s.size()-1 && s[i] == '2' && s[i+1] <= '6') {
            t.push_back(s[i+1] - '1' + 'a' + 20);
            decodeWays(res, t, s, i+2);
            t.pop_back();
        }
    }
    
    vector<string> decodeWays(string s)
    {
        vector<string> res;
        string t;
        decodeWays(res, t, s, 0);
        return res;
    }
    

  • 0
    R

    Here's my (probably slow) DP python solution.

    def alpha():
    # sets up letter code
        s = 'abcdefghijklmnopqrstuvwxyz'
        d = {}
        for x in range(1,27):
            d[str(x)] = s[x-1]
        return d
    
    
    def solution_helper(s, alpha, dp):
    # recursive function breaking up the problem
        if s in dp.keys():
            return dp[s]
        if len(s) == 0:
            return ['']
        if len(s) == 1:
            return [alpha[s]]
        
        if s[:2] in alpha.keys():
            dp[s] = [alpha[s[0]] + x for x in solution_helper(s[1:], alpha, dp)] + [alpha[s[:2]] + x for x in solution_helper(s[2:], alpha, dp)]
        else:
            dp[s] = [alpha[s[0]] + x for x in solution_helper(s[1:], alpha, dp)]
        return dp[s]
    
        
    def find_decoded(s):
    # The function that calls solution_helper, the solution.
        solutions = []
        dp = {}
        # dp format: (substring:[possible codes])
        sol = solution_helper(s, alpha(), dp)
        return len(sol), sol
    
    # Printing the example above
    print(find_decoded('1123'))
    
    

  • 0
    M
    public class Codes {
    	
    	public static void main(String[] args) {				
    		String input = "1123";		
    		calculateSets(input.length(), 0, "", input);
    	}
    	
    	static void calculateSets(int len, int currLen, String subset, String input){
    		if(len == currLen){
    			String output = "";
    			int currIndex = 0;
    			for (int i = 0; i < subset.length(); i++) {
    				int idx = 0;
    				if(subset.charAt(i) == '1'){
    					 idx = Integer.parseInt(input.substring(currIndex, 1 + currIndex));
    					 currIndex ++;
    				}
    				else{
    					 idx = Integer.parseInt(input.substring(currIndex, 2 + currIndex));
    					 currIndex = currIndex + 2;					  
    				}				
    				
    				idx --;
    				
    				output = output + (char) ('a' + idx);
    			}		
    			System.out.println(output);
    		}
    		else if(len > currLen){
    			calculateSets(len, currLen + 1, subset + "1", input);			
    			if(len >= currLen + 2 && Integer.parseInt(input.substring(currLen, currLen + 2)) < 27)
    				calculateSets(len, currLen + 2, subset + "2", input);			
    		}		
    	}
    }
    
    
    

  • 4
    M

    Java solution for all possible outputs -

    public class Solution {

    public Set<String> decode(String code) {
        Set<String> result = new HashSet<String>();
        helper("", code, result);
        return result;
    }
    
    
    public void helper(String prefix, String code, Set<String> result) {
    
        int len = code.length();
        if (len == 0) {
            result.add(prefix);
            return;
        }
        if (code.charAt(0) == '0')
            return;
    
        helper(prefix + (char)(code.charAt(0) - '1' + 'a'), code.substring(1), result);
    
        if (len >= 2) {
            int value = Integer.parseInt(code.substring(0, 2));
            if (value <= 26)
                helper(prefix + (char)(value - 1 +'a'), code.substring(2), result);
        }
    }
    

    }


  • 0
    public static void main(String[] args) {
            System.out.println(decodeToAlphabet("1123"));
        }
        private static List<String> decodeToAlphabet(String num) {
            List<String> res = new ArrayList<>();
            if (num == null || num.length() == 0) {
                return res;
            }
            dfs(num, 0, new StringBuilder(), res);
            return res;
        }
        private static void dfs(String num, int pos, StringBuilder path, List<String> res) {
            if (pos == num.length()) {
                res.add(path.toString());
                return;
            }
            int num1=  Integer.valueOf(num.substring(pos, pos + 1));
            path.append((char)('a' + num1 - 1));
            dfs(num, pos + 1, path, res);
            path.deleteCharAt(path.length() - 1);
            if (pos + 1 < num.length()) {
                int num2 = Integer.valueOf(num.substring(pos, pos + 2));
                if (10 <= num2 && num2 <= 26) {
                    path.append((char)('a' + num2 - 1));
                    dfs(num, pos + 2, path, res);
                    path.deleteCharAt(path.length() - 1);
                }
            }
        }
    

  • 0
    S

    python DFS solution.

    def helper(current, i, num_str, result):
        L = len(num_str)
        if i == L:
            result.append(current)
            return
        n_s = [int(num_str[i])]
        
        if i + 1 < len(num_str):
            n_s.append(int(num_str[i] + num_str[i+1]))
    
        # if use on digit, delta is 1, else 2
        delta = 1
        for n in n_s:
            if 1 <= n and n <= 26:
                c = chr(ord('a') + n -1)
                helper(current + c, i + delta, num_str, result)
            delta += 1
    
    
    def numDecodings(num_str):
        result = []
        helper("", 0, num_str, result)
        return result
    
    
    

  • 0
    M

    Java DFS

    public static List<String> decode(String txt) {
        List<String> result = new LinkedList<>();
        add(result, txt, new StringBuilder(), 0);
        return result;
      }
      
      public static void add(List<String> result, String txt, StringBuilder decodedTxtSoFar, int i) {
        if (i == txt.length()) {
          result.add(decodedTxtSoFar.toString());
          return;
        }
        
        int currentNumber = getNumber(txt, i, i+1);
        if (currentNumber > 0) {
          decodedTxtSoFar.append(decode(currentNumber));
          add(result, txt, decodedTxtSoFar, i+1);
          decodedTxtSoFar.deleteCharAt(decodedTxtSoFar.length() - 1);
        }
        
        int currentNumberWithNext = getNumber(txt, i, i + 2);
        if (currentNumberWithNext > 0 && currentNumberWithNext <= 26) {
          decodedTxtSoFar.append(decode(currentNumberWithNext));
          add(result, txt, decodedTxtSoFar, i+2);
          decodedTxtSoFar.deleteCharAt(decodedTxtSoFar.length() - 1);
        }
      }
      
      private static int getNumber(String txt, int start, int end) {
        if (start < 0 || end > txt.length()) {
          return -1;
        }
        return Integer.parseInt(txt.substring(start, end));
      }
      
      private static char decode(int v) {
        return (char) (v - 1 + 'a');
      }
    

  • 0
    S

    @salamanderrex This is wrong. Can you find it why?


  • 0
    A
    public class Solution {
        public static void main(String[] args) {
            String s = "1123";
            System.out.println(gen(s, ""));
        }
    
        static int gen(String s, String perm) {
            if (s.isEmpty()) {
                System.out.println(perm);
                return 1;
            }
            int c = 0;
            c += gen(s.substring(1), perm + code(Integer.parseInt(s.substring(0, 1))));
            if (s.length() > 1) {
                c += gen(s.substring(2), perm + code(Integer.parseInt(s.substring(0, 2))));
            }
            return c;
        }
    
        static char code(int num) {
            return (char) ('a' + num - 1);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.