{"id":1852,"date":"2016-03-02T17:14:14","date_gmt":"2016-03-02T09:14:14","guid":{"rendered":"http:\/\/boweihe.me\/?p=1852"},"modified":"2016-03-02T17:14:14","modified_gmt":"2016-03-02T09:14:14","slug":"leetcode-5-longest-palindromic-substring","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=1852","title":{"rendered":"LeetCode 5. Longest Palindromic Substring"},"content":{"rendered":"<p><strong>\u9898\u76ee\uff1a<\/strong>https:\/\/leetcode.com\/problems\/longest-palindromic-substring\/<br \/>\n<strong>\u601d\u8def\uff1a<\/strong><br \/>\n\u5206\u4e3a\u4e24\u79cd\u56de\u6587\uff0c\u4e00\u79cd\u662f&#8221;aba&#8221;\u7684\u5f62\u5f0f\uff0c\u53e6\u4e00\u79cd\u662f&#8221;aa&#8221;\u7684\u5f62\u5f0f\uff0c\u5f53\u7136\u4e86\uff0c&#8221;a&#8221;\u4e5f\u7b97\u662f\u56de\u6587.<br \/>\n\u6211\u7684\u60f3\u6cd5\u6307\u5b9a\u4e00\u4e2a\u5bf9\u79f0\u4e2d\u5fc3\uff0c\u7136\u540e\u5f80\u4e24\u8fb9\u641c\u7d22\uff0c\u8fd9\u6837\u80fd\u627e\u5230\u6700\u5927\u53ef\u80fd\u7684\u56de\u6587\u3002\u6216\u8bb8\u8fd8\u6709\u4e00\u79cd\u601d\u8def\u662f\u5229\u7528\u7c7b\u4f3c\u6808\u7684\u5bb9\u5668\u7684\uff0c\u4f46\u662f\u600e\u6837\u5224\u65ad&#8221;abcbaabcba&#8221;\u8fd9\u79cd\u5d4c\u5957\u578b\u7684\u5462\uff1f<br \/>\n<strong>\u4ee3\u7801\uff1a<\/strong><\/p>\n<pre class=\"lang:c++ decode:true \">class Solution {\npublic:\n\tstring longestP(string s, int pos, int type) {\n\t\t\/\/Type: 0- 'a', 1-'aa'\n\t\t\/\/Find palindrome at the position 'pos'\n\t\tint len = s.size();\n\t\tint posFront, posRear, maxLen;\n\t\tif (type == 0) {\n\t\t\tmaxLen = 1; \/\/'a'\n\t\t\tposFront = pos - 1;\n\t\t\tposRear = pos + 1;\n\t\t\tif (posFront &lt; 0)\n\t\t\t\treturn s;\n\t\t}\n\t\telse {\n\t\t\tmaxLen = 0;\n\t\t\tposFront = pos - 1;\n\t\t\tposRear = pos;\n\t\t}\n\t\twhile (posRear - posFront + 1 &lt;= len) {\n\t\t\tif (s[posFront] != s[posRear]) {\n\t\t\t\tif (maxLen == 0)\n\t\t\t\t\treturn \"\";\n\t\t\t\treturn s.substr(posFront + 1, posRear - posFront - 1);\n\t\t\t}\n\t\t\tposFront--;\n\t\t\tposRear++;\n\t\t\tmaxLen+=2;\n\t\t}\n\t\treturn s.substr(posFront + 1, posRear - posFront - 1);\n\t}\n\tstring longestPalindrome(string s) {\n\t\tint strSize = s.size();\n\t\tstring maxStr = s.substr(0,1);\n\t\tfor (int i = 1; i&lt;strSize; i++) {\n\t\t\tstring type1str = longestP(s, i, 0);\n\t\t\tstring type2str = longestP(s, i, 1);\n\t\t\tif (type1str.size() &gt; maxStr.size()) {\n\t\t\t\tmaxStr = type1str;\n\t\t\t}\n\t\t\tif (type2str.size() &gt; maxStr.size()) {\n\t\t\t\tmaxStr = type2str;\n\t\t\t}\n\t\t}\n\t\treturn maxStr;\n\t}\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\uff1ahttps:\/\/leetcode.com\/problems\/longest-palindromic-substring\/ \u601d\u8def\uff1a \u5206\u4e3a\u4e24\u79cd\u56de\u6587\uff0c\u4e00\u79cd\u662f&#8221;aba&#8221;\u7684\u5f62\u5f0f\uff0c\u53e6\u4e00\u79cd\u662f&#8221;aa&#8221;\u7684\u5f62\u5f0f\uff0c\u5f53\u7136\u4e86\uff0c&#8221;a&#8221;\u4e5f\u7b97\u662f\u56de\u6587. \u6211\u7684\u60f3\u6cd5\u6307\u5b9a\u4e00\u4e2a\u5bf9\u79f0\u4e2d\u5fc3\uff0c\u7136\u540e\u5f80\u4e24\u8fb9\u641c\u7d22\uff0c\u8fd9\u6837\u80fd\u627e\u5230\u6700\u5927\u53ef\u80fd\u7684\u56de\u6587\u3002\u6216\u8bb8\u8fd8\u6709\u4e00\u79cd\u601d\u8def\u662f\u5229\u7528\u7c7b\u4f3c\u6808\u7684\u5bb9\u5668\u7684\uff0c\u4f46\u662f\u600e\u6837\u5224\u65ad&#8221;abcbaabcba&#8221;\u8fd9\u79cd\u5d4c\u5957\u578b\u7684\u5462\uff1f \u4ee3\u7801\uff1a class Solution { public: string longestP(string s, int pos, int type) { \/\/Type: 0- &#8216;a&#8217;, 1-&#8216;aa&#8217; \/\/Find palindrome at the position &#8216;pos&#8217; int len = s.size(); int posFront, posRear, maxLen; if (type == 0) { maxLen = 1; \/\/&#8217;a&#8217; posFront = pos &#8211; 1; posRear = pos + 1; if [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[66],"class_list":["post-1852","post","type-post","status-publish","format-standard","hentry","category-technical","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1852","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1852"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1852\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1852"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1852"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1852"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}