SeniorCodeOccasionalNot answered yet
Strip smileys :-))) and :-((( from a message in one pass
Remove every smiley matching the pattern :-)+ or :-(+ from a message, in linear time, without using a regex. Do NOT handle nested smileys specially: :-:-)))((( becomes :-(((, not the empty string.
Requirements:
- Single pass, O(n); O(1) extra if mutating in place.
std::string removeSmileys(const std::string& s) {
// your code here
}Write the implementation.
Scan once as a small state machine. At each position check for : then - then a run of ) or (; if found, skip the whole token and continue past it, else copy the current character out. No backtracking into emitted text, so nesting is not collapsed. O(n).
- ✗Backtracking and collapsing nested smileys that the spec says to leave alone
- ✗Forgetting that the smiley needs a colon, a dash, AND a non-empty bracket run
- ✗Doing repeated erase passes, turning a one-pass problem into O(n²)
- →Why does avoiding backtracking give the no-nesting behaviour the spec wants?
- →How would you do it truly in place with a write index?
Contents
Task
Remove :-)+ and :-(+ smileys in one pass, without regex and without collapsing nesting.
Solution
std::string removeSmileys(const std::string& s) {
std::string out;
size_t i = 0, n = s.size();
while (i < n) {
if (i + 2 < n && s[i] == ':' && s[i+1] == '-' &&
(s[i+2] == ')' || s[i+2] == '(')) {
char br = s[i+2];
size_t j = i + 2;
while (j < n && s[j] == br) ++j; // bracket run
i = j; // skip the whole smiley
} else {
out.push_back(s[i++]); // ordinary character
}
}
return out;
}Key points
- Automaton:
:→-→ run of)or(, otherwise an ordinary char. - We never backtrack into output, so nesting is not collapsed.
- One pass, O(n).
Contents
