Pattern Matching

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

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






Video Solution

Code Solution

Run
 
Run
Id Name