Runtime: 16 ms, faster than 46.96% of C++ online submissions for Palindromic Substrings. Memory Usage: 9.9 MB, less than 48.00% of C++ online submissions for Palindromic Substrings.
解法二 - 從中間擴展
Leetcode solution 寫得還不錯,直接拿來用一下:
直接上個程式碼:
classSolution {public:intcountSubstrings(string s) {int N =s.length(), ans =0;for (int center =0; center <=2*N-1; ++center) {int left = center /2;int right = left + center %2;while (left >=0&& right < N &&s[left] ==s[right]) { ans++; left--; right++; } }return ans; }};
效率有夠猛:
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Palindromic Substrings. Memory Usage: 8.3 MB, less than 100.00% of C++ online submissions for Palindromic Substrings.
不過上面這個寫法的 left & right 值實在很不直覺,用下面這個寫法可能比較好懂:
class Solution { public: int countSubstrings(string s) { int count = 0;
for (int i = 0; i < s.size(); ++i) {
// odd length palindromes
//since center will be one element which both left and right start at
count += extract_palindrome(s, i, i);
// even length palindromes
// because center will have two elements (which must match) since left and right differ by 1
count += extract_palindrome(s, i, i + 1);
}
return count;
}
int extract_palindrome(string s, int left, int right) {
int count = 0;
while (left >= 0 && right < s.size() && s[left] == s[right]) {
--left;
++right;
// add palindrome to a hash since to deduplicate (keys can be iterated over later)
++count;
}
return count;
}