Wednesday, November 12, 2014

Facebook: Password combination

Given a dictionary based simple password, create all possible (special character) passwords based on a provide mapping. For example,
Input: face
Map: {a -> @, 4, A}
Output: f@ce, f4ce, fAce


Understand the problem:
This problem is a classical permutation and combination problem. It asks for outputting all possible combinations. Based on the problem description, if the mapping is not given, the output will retain the original character. E.g. f, c, and e will remain the same mapping in the output list. 

Code (Java):
import java.util.*;
public class Solution {
    public List<String> password(String str, Map<Character, String> dict) {
        List<String> result = new ArrayList<String>();
        
        if (str == null || str.length() == 0 || dict == null || dict.size() == 0) {
            return result;
        }
        
        StringBuilder sb = new StringBuilder();
        passwordHelper(str, 0, sb, dict, result);
        
        return result;
    }
    
    private void passwordHelper(String str, int start, StringBuilder sb, Map<Character, String> dict, List<String> result) {
        if (start >= str.length() && sb.length() == str.length()) {
            result.add(sb.toString());
            return;
        }
        
        for (int i = start; i < str.length(); i++) {
            char key = str.charAt(i);
            String value = dict.get(key);
            if (value != null) {
                for (int j = 0; j < value.length(); j++) {
                    sb.append(value.charAt(j));
                    passwordHelper(str, i + 1, sb, dict, result);
                    sb.deleteCharAt(sb.length() - 1);
                }
            } else {
                sb.append(key);
                passwordHelper(str, i + 1, sb, dict, result);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }

    public static void main(String[] args) {
      Solution sol = new Solution();

      String str = "face";
      Map<Character, String> dict = new HashMap<Character, String>();

      //dict.put('f', "f");
      dict.put('a', "aA4");
      //dict.put('c', "c");
      dict.put('e', "eE");

      List<String> result = sol.password(str, dict);

      for (String s : result) {
        System.out.println(s);
      }
    }
}


Discussion:
The problem itself is not hard. The only thing needs to be careful is when start >= str.length(), we also need to check the length of the string builder. That is because we don't want to output intermediate results.

Update on 11/16/14:
import java.util.*;
public class Solution {
    public List<String> password(String str, Map<Character, String> dict) {
        List<String> result = new ArrayList<String>();
        
        if (str == null || str.length() == 0 || dict == null || dict.size() == 0) {
            return result;
        }
        
        StringBuilder sb = new StringBuilder();
        passwordHelper(str, 0, sb, dict, result);
        
        return result;
    }
    
    private void passwordHelper(String str, int start, StringBuilder sb, Map<Character, String> dict, List<String> result) {
        if (start >= str.length()) {
            result.add(sb.toString());
            return;
        }
        
        //for (int i = start; i < str.length(); i++) {
            char key = str.charAt(start);
            String value = dict.get(key);
            if (value != null) {
                for (int j = 0; j < value.length(); j++) {
                    sb.append(value.charAt(j));
                    passwordHelper(str, start + 1, sb, dict, result);
                    sb.deleteCharAt(sb.length() - 1);
                }
            } else {
                sb.append(key);
                passwordHelper(str, start + 1, sb, dict, result);
                sb.deleteCharAt(sb.length() - 1);
            }
       // }
    }

    public static void main(String[] args) {
      Solution sol = new Solution();

      String str = "face";
      Map<Character, String> dict = new HashMap<Character, String>();

      //dict.put('f', "f");
      dict.put('a', "aA4");
      //dict.put('c', "c");
      dict.put('e', "eE");

      List<String> result = sol.password(str, dict);

      for (String s : result) {
        System.out.println(s);
      }
    }
}


No comments:

Post a Comment