[Wildcard Matching -Java] Using NFA


  • 0
    L
    public class Solution {
    public boolean isMatch(String s, String p) {
        if (s.length() == 0 && p.length() == 0) return true;
        if (p.length() == 0 ) return false;     
        
        HashSet<Integer> states = new HashSet<Integer>();        
        
        char c;      
        int j = 0;	        
        do{  
        	states.add(j);
        	if (states.contains(p.length())) return true;
        	c  = p.charAt(j++);
           
        }while(c == '*');
        if ( s.length()==0 ) return false;
        
        for (int i = 0; i < s.length(); i++){
            c = s.charAt(i);
            HashSet< Integer> newStates = new HashSet<Integer>();
            
            for (int state : states){
            	if (state >= p.length()) continue;
            	
                char ch = p.charAt(state);
                
                if (ch =='*'){
                    newStates.add(state);
                }// end if 
                
                if (ch == '?' || ch == c || ch == '*'){
                	newStates.add(state + 1);
                	 
                    int k = state +1;	        
                    while (k < p.length() && p.charAt(k) =='*'){  
                    	 k++;
                    	 if (k >= p.length()) return true;
                    	 newStates.add(k);                  	                        
                     }// end while  
                	 
                  }// end if 
                
               }// end for
           
              if (newStates.size()== 0) return false;
              states = newStates;
          }// end for
          if (states.contains(p.length()) ) return true;
          else return false;
        
        
        }// end isMatch
    
    }// end Solution

Log in to reply
 

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