Notes

tags: Two Pointers

tags: String,Two Pointers,LeetCode101 Two pointers move inwards, when we meet two different characters: Remove left character to see if the remains string still satisfied a valid palindrome. Remove right character to see if the remains string still satisfied a valid palindrome. Returns true if either one above two is true. class Solution { public: bool validPalindrome(string s) { for (int i = 0, j = s.size() -1; i < j; i++,j--) { if (s[i] != s[j]) { // remove left auto left = isPalindrome(s, i + 1, j); // remove right auto right = isPalindrome(s, i, j - 1); // return at here as we have traveled the string in the // invocation of isPalindrome. return right || left; } } return true; } private: bool isPalindrome(string & s, int i, int j) { for (; i < j; i++,j--) { if (s[i] != s[j]) { return false; } } return true; } };

tags: In-place WikiPedia: https://en.wikipedia.org/wiki/In-place%5Falgorithm Let see two examples before we go further: As above we can see, to reverse a array in-place, we just need swap each two elements in the array from both side to middle. The pseudo code from WikiPedia: function reverse_in_place(a[0..n-1]) for i from 0 to floor((n-2)/2) tmp := a[i] a[i] := a[n − 1 − i] a[n − 1 − i] := tmp The loop travels the array to the middle and swap each other in the list, two points we must be noticed: We stop the element at(not before): floor((n - 2) / 2), It’s both 1 of the two above figures. We swap current element with n - 1 - i.

tags: Algorithm

tags: In-place,LeetCode101,In-place Reverse class Solution { public: void reverseString(vector<char>& s) { if (s.size() == 1) { return; } for (int i = 0; i <= (s.size() - 2) / 2; ++i) { swap(s[s.size() - 1 - i], s[i]); } } };