Share My Swift 3 Based NFA Solution


  • 2
    B
    
    typealias State = Int
    
    struct Rule{
      let state:State
      let char:Character?
      let nextState:State
      
      func isApplyTo(state:State, char:Character?) -> Bool{
        return self.state == state && ( self.char == char || (self.char == "." && char != nil))
      }
    }
    
    struct NFARuleBook {
      let rules:[Rule]
      
      func nextStates(states:Set<State>, char:Character?) -> Set<State>{
        let stateList =  states.flatMap{ followRulesFor(state: $0, char: char) }
        return Set(stateList)
      }
      
      func followRulesFor(state:State, char:Character?) -> Set<State>{
        return Set(rulesFor(state: state, char: char).map{ $0.nextState })
      }
      
      func rulesFor(state:State, char:Character?) -> [Rule]{
        return rules.filter{ $0.isApplyTo(state:state, char:char) }
      }
      
      func followFreeMoves(states:Set<State>) -> Set<State>{
         let moreStates = nextStates(states: states, char: nil)
        if moreStates.isSubset(of: states){
          return states
        }else{
          return followFreeMoves(states: states.union(moreStates))
        }
      }
    }
    
    
    
    struct NFA{
      var currentStates:Set<State>
      let acceptStates:Set<State>
      let rulebook: NFARuleBook
      
      init(currentStates:Set<State>, acceptStates:Set<State>, rulebook:NFARuleBook) {
          self.currentStates = rulebook.followFreeMoves(states: currentStates)
          self.acceptStates = acceptStates
          self.rulebook = rulebook
      }
      
      var isAccepting:Bool{
          return currentStates.intersection(acceptStates).count > 0
      }
      
      mutating func read(char:Character){
        currentStates = rulebook.nextStates(states: currentStates, char: char)
        currentStates = rulebook.followFreeMoves(states: currentStates)
      }
      
      
      mutating func read(string:String){
        for char in string.characters{
          read(char: char)
        }
      }
    }
    
    enum Pattern{
      case plain(Character)
      case many(Character)
    }
    
    func parsePatterns(pattern:String) -> [Pattern]{
      let chars = pattern.characters
      var index = chars.startIndex
      var patterns:[Pattern] = []
      while index !=  chars.endIndex{
        let ch1 = chars[index]
        let index2 = chars.index(after: index)
        if index2 != chars.endIndex && chars[index2] == "*" {
          patterns.append(Pattern.many(ch1))
          index = chars.index(after: index2)
        }else{
          // a*a -> aa*
          patterns.append(Pattern.plain(ch1))
          index = chars.index(after: index)
        }
      }
      return patterns
    }
    
    
    func parseNFA(pattern:String) -> NFA{
      let patterns = parsePatterns(pattern: pattern)
      var rules:[Rule] = []
    
      var stateIndex = 0
      func newState() -> State{
        stateIndex = stateIndex + 1
        return  stateIndex
      }
      let startState = newState()
      var prevState = startState
      var acceptStates : Set<State> = []
      for p in patterns{
        let nextState = newState()
        switch p {
        case .plain(let ch):
          rules.append(Rule(state: prevState, char: ch, nextState: nextState))
          acceptStates = [nextState]
        case .many(let ch):
          //ab*a*c*a
          // have zero
          rules.append(Rule(state: prevState, char: nil, nextState: nextState))
          // has one
          rules.append(Rule(state: prevState, char: ch, nextState: nextState))
          // has many
          rules.append(Rule(state: nextState, char: ch, nextState: nextState))
          acceptStates.insert(nextState)
        }
        prevState = nextState
      }
    //  for rule in rules{
    //    print(rule)
    //  }
    //
      return NFA(currentStates: [startState], acceptStates: acceptStates, rulebook: NFARuleBook(rules: rules))
    }
    
    
    class Solution {
        func isMatch(_ s: String, _ p: String) -> Bool {
            if p.isEmpty{
                return s.isEmpty
            }
            var nfa = parseNFA(pattern: p)
            nfa.read(string:s)
            return nfa.isAccepting
        }
    }
    
    

  • 0
    F

    杀鸡焉用牛刀


Log in to reply
 

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