class Solution {
public:
bool pass(string input){
// helper function to test whether a string has adjacent chars inside of it
char prev = '\0';
for (char c : input){
if (c == prev) return false;
else prev = c;
}
return true;
}
string deDup(string & input){
if (input.empty() || input.size() == 1) return input;
size_t i = 0; // the element we are examining now
char curr = input[i];
while(i <= input.size()-1 && !input.empty()) {
curr = input[i];
if (input[i+1] != curr){
i++;
}
else {
while ((input[i+1] == curr) && (i <= input.size()-1))
input.erase(i+1, 1); // erase next character
input.erase(i, 1); // remove current character
i = 0;
}
}
// recursively call
while(!pass(input)){
deDup(input);
}
return input;
}
};
Many conditions to consider in this problem:
1. The outermost loop, we need to repeatedly test if the input has adjacent characters, after we remove ONE set of adjacent characters. i.e. the loop should start again immediately after the pointer detected and removed one set of adjacent characters, instead of restart after the pointer has reached the end of the input string.
2. In the end, we might have an empty string in the while loop. Since we will call input[i] in the next line, need to make sure the input string is not empty.
3. Where do we define the "curr"? We could define it at the first line of the while loop, or redefine it after we modify something. The first solution is better as I once forget to update the curr after erasing the current character - the index is still the same, but the curr will change!
4. Should we pass the input string by reference or by copy? Since we repeatedly remove elements of the string, it is better to pass by reference, or else note what do you want to return? If you want to preserve the original string you can make a copy of it and define a helper function.
1. The outermost loop, we need to repeatedly test if the input has adjacent characters, after we remove ONE set of adjacent characters. i.e. the loop should start again immediately after the pointer detected and removed one set of adjacent characters, instead of restart after the pointer has reached the end of the input string.
2. In the end, we might have an empty string in the while loop. Since we will call input[i] in the next line, need to make sure the input string is not empty.
3. Where do we define the "curr"? We could define it at the first line of the while loop, or redefine it after we modify something. The first solution is better as I once forget to update the curr after erasing the current character - the index is still the same, but the curr will change!
4. Should we pass the input string by reference or by copy? Since we repeatedly remove elements of the string, it is better to pass by reference, or else note what do you want to return? If you want to preserve the original string you can make a copy of it and define a helper function.
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.