Backtracking slution in JAVA - explanation in comments


  • 0
    S
    public static boolean match(String input, String pattern, int i_idx, int p_idx, HashMap<Character,String> mapping) {
    
          if(p_idx == pattern.length() && input.length() == i_idx) {
             for(int i = 0 ; i< pattern.length(); i++) {
                if(mapping.get(pattern.charAt(i)) == null) {
                   return false;
                }
             }
             return true;
          }
    
          if(p_idx == pattern.length()) {
             return false;
          }
    
          if(i_idx == input.length()) {
             return false;
          }
    
          Character p_char = pattern.charAt(p_idx);
          StringBuilder stringBuilder = new StringBuilder();
          for(int i = i_idx;  i < input.length(); i++) {
             stringBuilder.append(input.charAt(i));
    
             // if assigned to the current string, recurse
             if(mapping.get(p_char) != null && mapping.get(p_char).equals(stringBuilder.toString())) {
                return match(input, pattern, i+1, p_idx+1, mapping);
             }
    
             // current char is assigned and doesn't match the current string, keep expanding the string
             if(mapping.get(p_char) != null) {
                continue;
             }
    
             // current char and string are unassigned
             if(mapping.get(p_char) == null && !mapping.values().contains(stringBuilder.toString())) {
                mapping.put(p_char, stringBuilder.toString());
                if(match(input, pattern, i+1, p_idx+1, mapping)) {
                   return true;
                }
                else {
                   mapping.remove(p_char);
                }
             }else {
                continue; // continue trying more substrings
             }
          }
    
          return false;
    
       }
    

Log in to reply
 

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