JS Longest Palindrome Subsequence (DP)

JavaScript resolve longest palindrome subsequence problem by dynamic programming.

by Tinytsunami

HTML

<div id="demo">
  String = <input type="text" /> <button>Process</button>
  <pre>waiting for you input something...</pre>
</div>

CSS

body {
  color: #ffffff;
  background: #20262e;
  font-family: monospace, sans-serif;
}

#demo {
  width: 400px;
  padding: 5px;
}

#demo input {
  color: #ffffff;
  background: #20262e;
  outline: none;
  border: none;
  border-bottom: 1px solid #ffffff;
}

#demo pre {
  width: 400px;
  height: 100px;
  border: solid 1px #ffffff;
  overflow-y: scroll;
}

#demo button {
  color: #ffffff;
  background: #20262e;
  border: 1px solid #ffffff;
  outline: none;
}

#demo button:hover {
  color: #20262e;
  background: #ffffff;
  border: 1px solid #ffffff;
}

JavaScript

(function() {
  /* get elements */
  let root = document.getElementById("demo");
  let inputNode = root.getElementsByTagName("input")[0];
  let buttonNode = root.getElementsByTagName("button")[0];
  let outputNode = root.getElementsByTagName("pre")[0];

  /* check is palindrome */
  let checkPalindrome = function(text, a, b) {
    let len = b - a + 1;
    let half = parseInt(len / 2);
    for (let i = 0; i < half; i++)
      if (text[a + i] != text[b - i])
        return false;
    return true;
  };

  /* evaluation time for functions */
  let evaluationTime = function(f, callback) {
    let start = Date.now();
    let value = f();
    callback.call(this, value, (Date.now() - start));
  };

  /* get LPS by exhaustive */
  let main = function(text) {
    // create dp table
    let p = Array.from({length: text.length}, function() {
      return Array.from({length: text.length}, function() {
        return {
          len: -1,
          ans: ""
        };
      });
    });
    // resolve problem (get answer)
    let LPS = function(s, i, j) {
      if(p[i][j].len > 0) return p[i][j];
      if(i == j) {
      	p[i][j].len = 1;
        p[i][j].ans = s[i]; // = s[j]
      }
    	else if(i + 1 == j && s[i] == s[j]) {
      	p[i][j].len = 2;
        p[i][j].ans = `${s[i]}${s[j]}`;
      }
      else if(i != j && s[i] == s[j]) {
      	let tmp = LPS(s, i + 1, j - 1);
      	p[i][j].len = tmp.len + 2;
        p[i][j].ans = `${s[i]}${tmp.ans}${s[j]}`;
      }
      else { //(i != j && s[i] != s[j])
      	let tmp1 = LPS(s, i + 1, j);
        let tmp2 = LPS(s, i, j - 1);
        // select more length
        if(tmp1.len > tmp2.len)
        	p[i][j] = tmp1;
        else
        	p[i][j] = tmp2;
      }
      return p[i][j];
    };
    console.log(p);
    return LPS(text, 0, text.length - 1).ans;
  };

  /* user input and process*/
  buttonNode.onclick = function() {
    evaluationTime(function() {
      return main(inputNode.value);
    }, function(LPS, time) {
      if...