Pattern Matching

1. You are given a string and a pattern. 
2. You've to check if the string is of the same structure as pattern without using any regular 
     expressions.

Note -> Check out the question video and write the recursive code as it is intended without 
               changing signature. The judge can't force you but intends you to teach a concept.

Input Format

A String str
A pattern ptr

Output Format

Check the sample ouput and question video.

Question Video Constraints

1 <= length of str,ptr <= 20

Sample Input

graphtreesgraph
pep

Sample Output

p -> graph, e -> trees, . 

• Editorial

  We will solve the question with recursion and backtracking.

  At levels we will place the characters of the pattern. The options will be all the prefix substrings of the input string at that level. When we choose a prefix substring, we pass - original string - chosen substring to the next level.

  We will also use a HashMap to map the characters with the string we choose. If we encounter a character that was used before, we will check whether the string that we mapped before is present as a prefix substring or not. If it is not, we cannot continue and if it is, we will continue with the string that was chosen before.

  Signature -

  public static void solution(String str, String pattern, HashMap map, String op)

  str - input string at each level.

  pattern - input pattern at each level

  map - HashMap to store the characters with

  the string we match

  op - input pattern (used in base case)

  Code -

  public static void solution(String str, String pattern, 
                                  HashMap
   map, String op)
                                      {
                                          if(pattern.length() == 0){
                                              if(str.length() == 0){
                                                  boolean[] arr = new boolean[26];
                                                  for(int i = 0 ; i < op.length(); i++) {
                                                      char ch = op.charAt(i);
                                                      if(arr[ch - 'a'] == false) {
                                                          arr[ch - 'a'] = true;
                                                          System.out.print(ch + " -> " + map.get(ch) + ", ");
                                                      }
                                                  }
                                                  System.out.println(".");
                                              }
                                              return;
                                          }
                                  
                                          char chp = pattern.charAt(0);
                                          String rop = pattern.substring(1);
                                          
                                          if(!map.containsKey(chp)){
                                              //if character is coming for the first time
                                              for(int i = 0 ; i < str.length(); i++){
                                                  String fh = str.substring(0, i + 1);
                                                  String ros = str.substring(i + 1);
                                  
                                                  map.put(chp, fh);
                                                  solution(ros,rop,map,op);
                                                  map.remove(chp);
                                              }
                                          }else{
                                              //if character has already appeared 
                                              String prevmatching = map.get(chp);
                                              String nextsubstring = str.length() >= prevmatching.length() ? 
                                  str.substring(0, prevmatching.length()) : "-1";
                                              if(prevmatching.equals(nextsubstring)){
                                                  String ros = str.substring(prevmatching.length());
                                                  solution(ros, rop, map,op);
                                              }
                                          }
                                      }

  java falseCode Explained -

  We will first check whether the current character has already been mapped before or not.

  Case 1 -

  The character is coming for the first time -

  We will use a FOR LOOP for the prefix substring. We will assign every prefix substring to the current character and make a call for the next level. In pre - order we will add the string we assigned to the character in HashMap and in post - order we will remove it from the HashMap.

  Case 2 -

  The character is not coming for the first time -

  We will check whether the string that we mapped the character before is the prefix substring of the str. If it is, make a call for the next level. If not, do not make any call.

  Base Case -

  When we have used all the characters (length of the pattern is zero), we will hit base case.

  If we have used whole str (length of str is zero), it means every character of the pattern is assigned to some string of str. As in the required output, we will print the unique characters of the pattern with the help of HashSet. Character that come first has to be printed first, therefore we will use op for that.

  We will return from the base case.

• Asked in Companies
• Related Topics