(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.


  • 1
    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);			
    		}		
    	}
    }
    
    
    

  • 5
    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);
        }
    }
    

  • 0
    A

    Here is my Swift code.

        func interpret(num: String) -> [String] {
            let text:[Int] = num.characters.map {Int(String($0))!}
            var mark:[[String]] = []
            
            for index in 0..<text.count {
                if index == 0 {
                    mark.append([String(UnicodeScalar(UInt8(text[index] + 96)))])
                } else {
                    var list = [String]()
                    if text[index] == 0 {
                        // Assure the previous number should be 1 or 2, otherwise, it is invalid.
                        let c = String(UnicodeScalar(UInt8(text[index] + 96 + 10 * text[index - 1])))
                        if index > 1 {
                            for option in mark[index - 2] {
                                list.append(option + c)
                            }
                        } else {
                            list.append(c)
                        }
                    } else {
                        if text[index] + text[index-1] * 10 <= 26, text[index-1] != 0 {
                            let c = String(UnicodeScalar(UInt8(text[index] + 96 + 10 * text[index - 1])))
                            if index > 1 {
                                for option in mark[index - 2] {
                                    list.append(option + c)
                                }
                            } else {
                                list.append(c)
                            }
                        }
                        let c = String(UnicodeScalar(UInt8(text[index] + 96)))
                        for option in mark[index - 1] {
                            list.append(option + c)
                        }
                    }
                    mark.append(list)
                }
            }
            return mark[text.count - 1]
        }
    

  • 0
    A
    private List<String> getDecodings(String s){
        List<String> decodings = new ArrayList<String>(){{
          add("");
        }};
        if(s==null || s.length()==0) return decodings;
        
        // decode first digit
        int first = s.charAt(0)-'0';
        String decode1 = String.valueOf((char)('a'+first-1));
        
        // decode first 2 digits together if possible
        String decode2 = "";
        if(s.length()>1) {
          int second = s.charAt(1)-'0';
          if(first*10+second<=26) decode2 = String.valueOf((char)('a'+first*10+second-1));
        }
        
        // recursively get future decodings and append current decode to them
        List<String> decodings1 = getDecodings(s.substring(1));
        for(String d: decodings1){
          decodings.add(decode1 + d);
        }
        
        if(!decode2.equals("")){
          List<String> decodings2 = getDecodings(s.substring(2));
          for(String d: decodings2){
            decodings.add(decode2 + d);
          }
        }
        decodings.remove("");
        
        return decodings;
      }
    

  • 0
    C

    This is C++11 program. It uses recursion.
    I have skipped digit validations like digit cannot be 0 or greater than 6. Also need to handle cases like '32', '41', anything bigger than 26 etc. It will be like adding few more checks but this code talks about general idea.

    #include <iostream>
    #include <string>
    #include <set>
    
    using namespace std;
    set<string> result;
    
    void combination(string tmp, string input)
    {
        int len = input.length();
        if (len == 0) {
            result.insert(tmp);
            return;
        }
        
        for(int i=1; i<=2; i++) {
            if (len < i)
                return;
            combination(tmp + char(stoi(input.substr(0, i)) - 1 + 'a'), input.substr(i));
        }
            
    }
    
    int main()
    {
        string input = "1123";
        string tmp = "";
        combination(tmp, input);
        for(auto i : result)
            cout << i << endl;
        return 0;
    }
    

Log in to reply
 

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