291.txt

Given a pattern and a string s, return true if s matches the pattern.

A string s matches a pattern if there is some bijective mapping of single characters to strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.

 

Example 1:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"
Example 2:

Input: pattern = "aaaa", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "asd"
Example 3:

Input: pattern = "abab", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "a"
'b' -> "sdasd"
Note that 'a' and 'b' cannot both map to "asd" since the mapping is a bijection.
Example 4:

Input: pattern = "aabb", s = "xyzabcxzyabc"
Output: false
 

Constraints:

0 <= pattern.length <= 20
0 <= s.length <= 50
pattern and s consist of only lower-case English letters.









class Solution {
    String t[]=new String[26];
    boolean res=false;
    public boolean wordPatternMatch(String pattern, String s) {
        for(int i=0;i<t.length;i++){
            t[i]="";
        }
        dfs(pattern,s,0,0,new HashSet<>());
        return res;
    }
    
    public void dfs(String pattern, String s,int pindex,int sindex,Set<String>set){
        if(pindex>=pattern.length()){
            if(sindex>=s.length()){
                res=true;
            }
            return;
        }
        if(sindex>=s.length())return;
        char c=pattern.charAt(pindex);
        if(t[c-'a'].length()!=0){
            String mat=t[c-'a'];
            if(sindex+mat.length()-1>=s.length()||!(s.substring(sindex,sindex+mat.length()).equals(mat)))return;
            dfs(pattern,s,pindex+1,sindex+mat.length(),set);
            
        }
        else{
            StringBuilder str=new StringBuilder();
            for(int i=sindex;i<s.length();i++){
                str.append(s.charAt(i));
                String ss=str.toString();
                if(set.contains(ss))continue;
                set.add(ss);
                t[c-'a']=ss;
                dfs(pattern,s,pindex+1,i+1,set);
                t[c-'a']="";
                set.remove(ss);
            }
            
        }
        
    }
}