Show my DFS solution with pruning


  • 0
    U
    public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        int level=pattern.length();
         HashMap<Character,Integer> cMap=new HashMap<Character,Integer>();
         HashMap<String,Integer> sMap=new HashMap<String,Integer>();
        return DFSCmp(pattern,str,0,0,cMap,sMap);
    }
    public boolean DFSCmp(String pattern,String str,int level,int start,HashMap<Character,Integer>cMap,HashMap<String,Integer> sMap)
    {
        if(level==pattern.length())
        {
          if(start!=str.length())
          return false;
          else
           return true;
        }
        else
        {
            int length=str.length()-start;
            boolean find=false;
              if(length<pattern.length()-level)
                 return false;
            for(int i=1;i<=length;i++)
            {
                boolean cExit=cMap.containsKey(pattern.charAt(level));
                boolean sExit=sMap.containsKey(str.substring(start,start+i));
                boolean equal=(cExit==sExit);
                if(equal&&cExit)
                 {
                     int cRecP=cMap.get(pattern.charAt(level));
                     int sRecP=sMap.get(str.substring(start,start+i));
                     if(cRecP==sRecP)
                      {
                    HashMap<Character,Integer> ctemp=new HashMap<Character,Integer>(cMap);
                     HashMap<String,Integer> stemp=new HashMap<String,Integer>(sMap);
                    cMap.put(pattern.charAt(level),level);
                    sMap.put(str.substring(start,start+i),level);
                    find=find||DFSCmp(pattern,str,level+1,start+i,cMap,sMap);
                    if(find)
                     return find;
                    cMap=ctemp;
                     sMap=stemp;
                      }
                 }
                 else if(equal&&!cExit)
                 {
                    HashMap<Character,Integer> ctemp=new HashMap<Character,Integer>(cMap);
                     HashMap<String,Integer> stemp=new HashMap<String,Integer>(sMap);
                    cMap.put(pattern.charAt(level),level);
                    sMap.put(str.substring(start,start+i),level);
                    find=find||DFSCmp(pattern,str,level+1,start+i,cMap,sMap);
                    if(find)
                     return find;
                    cMap=ctemp;
                     sMap=stemp; 
                 }
            }
            return false;
        }
    }
    

    }


Log in to reply
 

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