#562

Committed 18 Jun 2023 05:07PM UTC coverage: 97.602%. First build

Build # #562

Build Type

push

travis-ci

Committed by

web-flow

Commit Message

Merge pull request #207 from Ahtaxam/master

Add 3-sum problem with improvement issue #208

Run Details

525 of 541 branches covered (97.04%)

Branch coverage included in aggregate %.

21 of 21 new or added lines in 1 file covered. (100.0%)

1266 of 1294 relevant lines covered (97.84%)

32.93 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.81

/src/_DataStructures_/Trees/SuffixTree/index.js

/* eslint-disable max-len */
/* eslint-disable no-restricted-syntax */
/* eslint-disable no-plusplus */
/*
Implemented by watching this conceptually video: https://www.youtube.com/watch?v=VA9m_l6LpwI

Suffix for banana are :
banana
anana
nana
ana
na
a

Constructing a suffix tree is O(n*d) where d is length of max string

Searching a suffix of a string is O(d) where d is length of suffix string.
If found then return the index, else return -1

*/

const alphabets = 'abcdefghijklmnopqrstuvwxyz';
class Node {
  constructor(value, isEnd, index) {
    this.data = value;
    this.isEnd = isEnd;
    this.index = index;
    this.next = new Map();
  }
}

class SuffixTree {
  constructor(string) {
    this.head = new Node();
    this.string = string.toLowerCase();
  }

  constructSuffixTree() {
    const { string } = this;
    let currentString = '';
    for (let i = string.length - 1; i >= 0; i -= 1) {
      currentString = string[i] + currentString;
      let j = 0;
      let currentNode = this.head;
      while (j < currentString.length) {
        if (!currentNode.next.has(currentString[j])) {
          let nextString = '';
          while (j < currentString.length) {
            nextString += currentString[j];
            j++;
          }
          currentNode.next.set(nextString[0], new Node(nextString, true, i));
          break;
        } else {
          let k = 0;
          const partialMatchNode = currentNode.next.get(currentString[j]);
          const partialMatchString = partialMatchNode.data;

          let matchString = '';
          while (
            k < partialMatchString.length &&
            j < currentString.length &&
            partialMatchString[k] === currentString[j]
          ) {
            matchString += currentString[j];
            k++;
            j++;
          }

          let diffString = '';
          while (k < partialMatchString.length) {
            diffString += partialMatchString[k];
            k++;
          }

          partialMatchNode.data = matchString;
          if (diffString) {
            const oldMap = partialMatchNode.next;
            const newNode = new Node(diffString, partialMatchNode.isEnd, partialMatchNode.index);
            const alphabetsArray = alphabets.split('');

            for (const char of alphabetsArray) {
              if (oldMap.has(char)) {
                newNode.next.set(char, oldMap.get(char));
              }
            }
            partialMatchNode.next = new Map();
            partialMatchNode.next.set(diffString[0], newNode);
            partialMatchNode.isEnd = false;
            partialMatchNode.index = null;
          }

          if (partialMatchNode.next.has(currentString[j])) {
            currentNode = partialMatchNode;
          } else {
            let nextString = '';
            while (j < currentString.length) {
              nextString += currentString[j];
              j++;
            }
            partialMatchNode.next.set(nextString[0], new Node(nextString, true, i));
            break;
          }
        }
      }
    }
  }

  findSubstring(string) {
    string = string.toLowerCase();
    if (!this.head.next.has(string[0])) {
      return -1;
    }

    let currentNode = this.head.next.get(string[0]);
    let currentNodeValue = currentNode.data;

    let i = 0;
    let j = 0;

    while (i < string.length) {
      j = 0;
      while (i < string.length && j < currentNodeValue.length && string[i++] === currentNodeValue[j++]);

      if (i === string.length && j === currentNodeValue.length && currentNode.isEnd) {
        return currentNode.index;
      }

      if (currentNode.next.has(string[i])) {
        currentNode = currentNode.next.get(string[i]);
        currentNodeValue = currentNode.data;
      } else {
        return -1;
      }
    }
    return -1;
  }
}

// const st = 'CatatecheeseMouseatecheesetooCatatemousetoo';
// const s = new SuffixTree(st);
// s.constructSuffixTree();

// for (let i = 0; i < st.length; i++) {
//   const e = st.substring(i);
//   if (s.findSubstring(e) !== i) {
//     console.log(e, i, s.findSubstring(e));
//   }
// }

module.exports = SuffixTree;

1	/* eslint-disable max-len */
2	/* eslint-disable no-restricted-syntax */
3	/* eslint-disable no-plusplus */
4	/*
5	Implemented by watching this conceptually video: https://www.youtube.com/watch?v=VA9m_l6LpwI
6
7	Suffix for banana are :
8	banana
9	anana
10	nana
11	ana
12	na
13	a
14
15	Constructing a suffix tree is O(n*d) where d is length of max string
16
17	Searching a suffix of a string is O(d) where d is length of suffix string.
18	If found then return the index, else return -1
19
20	*/
21
22	const alphabets = 'abcdefghijklmnopqrstuvwxyz';	1✔
23	class Node {
24	constructor(value, isEnd, index) {
25	this.data = value;	50✔
26	this.isEnd = isEnd;	50✔
27	this.index = index;	50✔
28	this.next = new Map();	50✔
29	}
30	}
31
32	class SuffixTree {
33	constructor(string) {
34	this.head = new Node();	5✔
35	this.string = string.toLowerCase();	5✔
36	}
37
38	constructSuffixTree() {
39	const { string } = this;	5✔
40	let currentString = '';	5✔
41	for (let i = string.length - 1; i >= 0; i -= 1) {	5✔
42	currentString = string[i] + currentString;	39✔
43	let j = 0;	39✔
44	let currentNode = this.head;	39✔
45	while (j < currentString.length) {	39✔
46	if (!currentNode.next.has(currentString[j])) {	88✔
47	let nextString = '';	17✔
48	while (j < currentString.length) {	17✔
49	nextString += currentString[j];	58✔
50	j++;	58✔
51	}
52	currentNode.next.set(nextString[0], new Node(nextString, true, i));	17✔
53	break;	17✔
54	} else {
55	let k = 0;	71✔
56	const partialMatchNode = currentNode.next.get(currentString[j]);	71✔
57	const partialMatchString = partialMatchNode.data;	71✔
58
59	let matchString = '';	71✔
60	while (	71✔
61	k < partialMatchString.length &&	311✔
62	j < currentString.length &&
63	partialMatchString[k] === currentString[j]
64	) {
65	matchString += currentString[j];	76✔
66	k++;	76✔
67	j++;	76✔
68	}
69
70	let diffString = '';	71✔
71	while (k < partialMatchString.length) {	71✔
72	diffString += partialMatchString[k];	16✔
73	k++;	16✔
74	}
75
76	partialMatchNode.data = matchString;	71✔
77	if (diffString) {	71✔
78	const oldMap = partialMatchNode.next;	6✔
79	const newNode = new Node(diffString, partialMatchNode.isEnd, partialMatchNode.index);	6✔
80	const alphabetsArray = alphabets.split('');	6✔
81
82	for (const char of alphabetsArray) {	6✔
83	if (oldMap.has(char)) {	156!
84	newNode.next.set(char, oldMap.get(char));	×
85	}
86	}
87	partialMatchNode.next = new Map();	6✔
88	partialMatchNode.next.set(diffString[0], newNode);	6✔
89	partialMatchNode.isEnd = false;	6✔
90	partialMatchNode.index = null;	6✔
91	}
92
93	if (partialMatchNode.next.has(currentString[j])) {	71✔
94	currentNode = partialMatchNode;	49✔
95	} else {
96	let nextString = '';	22✔
97	while (j < currentString.length) {	22✔
98	nextString += currentString[j];	55✔
99	j++;	55✔
100	}
101	partialMatchNode.next.set(nextString[0], new Node(nextString, true, i));	22✔
102	break;	22✔
103	}
104	}
105	}
106	}
107	}
108
109	findSubstring(string) {
110	string = string.toLowerCase();	14✔
111	if (!this.head.next.has(string[0])) {	14✔
112	return -1;	3✔
113	}
114
115	let currentNode = this.head.next.get(string[0]);	11✔
116	let currentNodeValue = currentNode.data;	11✔
117
118	let i = 0;	11✔
119	let j = 0;	11✔
120
121	while (i < string.length) {	11✔
122	j = 0;	20✔
123	while (i < string.length && j < currentNodeValue.length && string[i++] === currentNodeValue[j++]);	20✔
124
125	if (i === string.length && j === currentNodeValue.length && currentNode.isEnd) {	20✔
126	return currentNode.index;	9✔
127	}
128
129	if (currentNode.next.has(string[i])) {	11✔
130	currentNode = currentNode.next.get(string[i]);	9✔
131	currentNodeValue = currentNode.data;	9✔
132	} else {
133	return -1;	2✔
134	}
135	}
136	return -1;	×
137	}
138	}
139
140	// const st = 'CatatecheeseMouseatecheesetooCatatemousetoo';
141	// const s = new SuffixTree(st);
142	// s.constructSuffixTree();
143
144	// for (let i = 0; i < st.length; i++) {
145	// const e = st.substring(i);
146	// if (s.findSubstring(e) !== i) {
147	// console.log(e, i, s.findSubstring(e));
148	// }
149	// }
150
151	module.exports = SuffixTree;	1✔

knaxus / problem-solving-javascript / #562

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous