I’m currently reading the official editorial for the 2023 january gold p1 find and replace.
I pretty much understand all of it, except the one part when they state:
Note that its very important that leaf nodes only contain individual letters and not empty strings. Changing the one line Node* result = nullptr; to Node* result = new Node(); results in an O(NM) solution instead because the empty string gets repeated many times in S but doesnt count toward its length.
I recently switched from java to c++, and am not familiar with why this would make a difference(I’ve tried searching online). Can someone please clarify this?
Thanks in advance