Missing Test Case - 3045. Count Prefix and Suffix Pairs II #33888
Description
LeetCode Username
jpkmnmstr
Problem Number, Title, and Link
- Count Prefix and Suffix Pairs II https://leetcode.com/problems/count-prefix-and-suffix-pairs-ii
Bug Category
Missing test case (Incorrect/Inefficient Code getting accepted because of missing test cases)
Bug Description
In my prefix length array creation, I decided to try and test setting j to 0 instead of finding the next best border length. This hacky code passed when it should have failed. An example test-case where the hack fails is:
countPrefixSuffixPairs(["aa", "aabaaa"]) so add this test-case, and maybe some other similar ones too.
Language Used for Code
JavaScript
Code used for Submit/Run operation
function buildPi(s) {
const n = s.length;
const pi = new Array(n);
let j=pi[0]=0;
for (let i = 1; i < n; i++) {
/*while (j > 0 && s[i] != s[j])//correct version
j = pi[j - 1];*/
if(s[i]!=s[j])//hacky incorrect version, passes test cases though
j=0;
pi[i] = s[i]==s[j]?++j:j;
}
return pi;
}
var countPrefixSuffixPairs = function(words) {
// Trie node structure
function Node() {
this.next = Object.create(null); // char -> Node, stores all of the CHILDREN (next characters)
this.countEnd = 0; // how many words end at this node
}
const root = new Node();
let ans = 0;
// Insert a word into the trie
function insert(word) {
let node = root;
for (let ch of word) {
if (!node.next[ch]) node.next[ch] = new Node();
node = node.next[ch];
}
node.countEnd++;
}
for (const w of words) {
const n = w.length;
// 1) Compute all border lengths (proper borders: length < n)
const pi = buildPi(w);
const isBorder = new Array(n + 1).fill(false);
let len = pi[n - 1];
while (len > 0) {
isBorder[len] = true;
len = pi[len - 1];
}
// 2) Walk down the trie following the prefix of w,
// and whenever the current prefix length is a border,
// add the number of previous words ending here.
let node = root;
for (let i = 0; i < n; i++) {
const ch = w[i];
node = node.next[ch];
if (!node) break; // no longer prefixes exist in trie; stop
const prefixLen = i + 1;
if (isBorder[prefixLen]) {
ans += node.countEnd;
}
// NOTE: do *not* treat full length here, that's handled below
}
// 3) Handle the "full word" case:
// A word always starts and ends with itself,
// so any earlier identical words are also valid pairs.
// That corresponds to prefix length = n.
node = root;
let exists = true;
for (let i = 0; i < n; i++) {
const ch = w[i];
node = node.next[ch];
if (!node) {
exists = false;
break;
}
}
if (exists) {
ans += node.countEnd;
}
// 4) Finally, insert current word so it can contribute to future words
insert(w);
}
return ans;
};Expected behavior
The test cases are currently incomplete. The hacky version fails the test case countPrefixSuffixPairs(["aa", "aabaaa"]) so at least add that one!
Screenshots
No response
Additional context
No response