Hello,
I was implementing a simple Trie when I found a behavior that I didn't understand. I followed the program using a debugger, the issue seems to be in the insert
function. I explained the issue in code comments.
struct Trie{
struct Node{
int id, nxt[26];
Node(int id) : id(id)
{
memset(nxt, -1, sizeof(nxt));
}
};
vector<Node> v;
vector<bool> leaf;
void init()
{
v.clear();
leaf.clear();
addNode();
}
int addNode()
{
v.push_back(v.size());
leaf.push_back(false);
return (int)(v.size()) - 1;
}
int getSizeMinusOne()
{
return (int)(v.size()) - 1;
}
void insert(const string &s)
{
int cur = 0;
for (char c : s)
{
c -= 'a';
if (v[cur].nxt[c] == -1)
{
// Note I only use one of the following NOT both at the same time
// Approach (1)
// v[cur].nxt[c] doesn't get updated. Stays -1 and RTEs later on due to out of boundary access
v[cur].nxt[c] = addNode();
// Approach (2)
// works fine
addNode();
v[cur].nxt[c] = getSizeMinusOne();
}
cur = v[cur].nxt[c];
}
leaf[cur] = true;
}
};
I also found out that both approaches seem to work find when changing the array nxt
to a vector instead of an array. Could someone explain why this happens when nxt
is an array? And why approach (2) works fine even if nxt
is an array?