Skip to content

Instantly share code, notes, and snippets.

@cAstraea
Last active February 6, 2017 15:20
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save cAstraea/c4e1756c3fc76535879ab32015d65fd6 to your computer and use it in GitHub Desktop.
Save cAstraea/c4e1756c3fc76535879ab32015d65fd6 to your computer and use it in GitHub Desktop.
breakwords dynamic javascript implementation https://www.youtube.com/watch?v=WepWFGxiwRs
function StringBuffer() {
this.__strings__ = [];
}
StringBuffer.prototype.append = function (str) {
this.__strings__.push(str);
};
StringBuffer.prototype.toString = function () {
return this.__strings__.join('');
};
function breakWord(stringToBreak, dictionary) {
const matrix = [];
const len = stringToBreak.length;
for (let i = 0; i < stringToBreak.length; i++) {
matrix[i] = new Array(stringToBreak.length);
}
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
matrix[i][j] = -1; // -1 indicates string between i to j cannot be split
}
}
for (let l = 1; l <= len; l++) {
for (let i = 0; i < (len - l) + 1; i++) {
const j = i + (l - 1);
const str = stringToBreak.substring(i, j + 1);
// if string between i to j is in dictionary matrix[i][j] is true
if (dictionary.has(str)) {
matrix[i][j] = i;
continue;
}
// find a k between i+1 to j such that matrix[i][k-1] && matrix[k][j] are both true
for (let k = i + 1; k <= j; k++) {
if (matrix[i][k - 1] !== -1 && matrix[k][j] !== -1) {
matrix[i][j] = k;
break;
}
}
}
}
if (matrix[0][len - 1] === -1) {
return null;
}
const buffer = new StringBuffer();
let i = 0;
const j = len - 1;
while (i < j) {
const k = matrix[i][j];
if (i === k) {
// console.log(stringToBreak.substring(i, j + 1));
buffer.append(stringToBreak.substring(i, j + 1));
break;
}
// console.log(`${stringToBreak.substring(i, k) } `);
buffer.append(`${stringToBreak.substring(i, k)} `);
i = k;
}
return buffer.toString();
}
const mySet = new Set();
mySet.add('a');
mySet.add('i');
mySet.add('am');
mySet.add('ace');
mySet.add('you');
mySet.add('code');
mySet.add('love');
mySet.add('to');
const inputString = 'codeiloveto';
const result = breakWord(inputString, mySet);
console.log(result);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment