Bedbathandbeyond problem

by chrisJamesC

JavaScript

const dict = ["hand", "bed","bat","bath","and","beyond","help"]

// Simple solution 
const simple = (s) => {
  if(!s.length) return true; 
  for(let i=s.length; i>0; i--) {
  	if(dict.includes(s.substring(0,i)) && simple(s.substring(i,s.length))) return true 
  }
	return false
} 

// A solution which uses a bitmap. 
const bitmap = (s) => {
  let base = [];
  for(let i=0; i<s.length; i++) {
    if(dict.includes(s.substring(0,i+1))) {
      base[i] = true;
    } else {
      for(let j=0; j<i && !base[i]; j++) {
        if(base[j] && dict.includes(s.substring(j+1,i+1))) {
          base[i] = true; 
        }
      }
    }
  }
  return base[s.length-1] || false
}

const example = "bedbathandbeyond"
const res1 = simple(example) && bitmap(example)
const broken  = "bedbathandbelond"
const res2 = !(simple(broken) || bitmap(broken))
const william = "bedbathelp"
const res3 = simple(william) && bitmap(william)
document.body.innerHTML = res1 && res2 && res3;