ngram.js

// 字符串匹配，"foo foo bar" "aab" return true! 

//a->b, a<-b

//hash[foo] = a
//hash[bar] = b

//'a b', 'a'

function isPatternMatch(_a, b){
  //console.log(_a, b)
  if(_a.length !== b.length) return false
  
  var hash = {}
  
  for(var i = 0; i <_a.length; i++){
    
    var word = _a[i]
    
    if(hash.hasOwnProperty(word)){
      if(hash[word] !== b[i]) return false
    }else{
      hash[word] = b[i]
    }
  }
  
  hash = {}
  for(i = 0; i < b.length; i++){
    if(hash.hasOwnProperty(b[i])){
      if(hash[b[i]] !== _a[i]) return false
    }else{
      hash[b[i]] = _a[i]
    }
  }
  
  return true
  
}

// console.log(isPatternMatch(['b', 'b', 'c'], "aab")) //=> true
// console.log(isPatternMatch(['foo', 'bar', 'bar'], "aaa")) //=> false

// follow up: 第一个字符串不能用空格分开，一个char不确定match多长的string
// “foofoobar” “aab” return true

function isPatternMatch1(a, b){
  return helper([], a, b, 0)
}

function helper(list, a, b, begin){
  if(begin === a.length && list.length === b.length && isPatternMatch(list, b)){
    return true
  }
  
  if(list.length >= b.length) return false
  
  for(var i = begin; i < a.length; i++){
    var prefix = a.substring(begin, i+1) 
    list.push(prefix)
    if(helper(list, a, b, i + 1)) return true
    list.pop()    
  }
  
  return false
}
//thoughts:
//search all the posibble cutting, if one matches(a->b, a<-b) return true
//in the end return false

console.log(isPatternMatch1("bbc", "aab")) //=> true
console.log(isPatternMatch1("foobarbar", "aaa")) //=> false
console.log(isPatternMatch1("foobarbar", "baa")) //=> true