add 647

fishercoder1534 · fishercoder1534 · commit 359dcd05334d · 2017-07-24T16:00:25.000-07:00
diff --git a/README.md b/README.md
@@ -21,6 +21,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |  #  |      Title     |   Solutions   | Time          | Space         | Difficulty  | Tag          | Notes
 |-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
 |648|[Replace Words](https://leetcode.com/problems/replace-words/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_648.java) | O(n) |O(n) | Medium | Trie
+|647|[Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_647.java) | O(n^2) |O(1) | Medium | DP
 |646|[Maximum Length of Pair Chain](https://leetcode.com/problems/maximum-length-of-pair-chain/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_646.java) | O(nlogn) |O(1) | Medium | DP
 |645|[Set Mismatch](https://leetcode.com/problems/set-mismatch/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_645.java) | O(nlogn) |O(1) | Easy | 
 |644|[Maximum Average Subarray II](https://leetcode.com/problems/maximum-average-subarray-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_644.java) | |O(1) | Hard | Binary Search
diff --git a/src/main/java/com/fishercoder/solutions/_647.java b/src/main/java/com/fishercoder/solutions/_647.java
@@ -0,0 +1,45 @@
+package com.fishercoder.solutions;
+
+/**
+ * 647. Palindromic Substrings
+ *
+ *  Given a string, your task is to count how many palindromic substrings in this string.
+ *  The substrings with different start indexes or end indexes are counted
+ *  as different substrings even they consist of same characters.
+
+ Example 1:
+ Input: "abc"
+ Output: 3
+ Explanation: Three palindromic strings: "a", "b", "c".
+
+ Example 2:
+ Input: "aaa"
+ Output: 6
+ Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
+
+ Note:
+ The input string length won't exceed 1000.
+
+ */
+public class _647 {
+
+    /**reference: https://discuss.leetcode.com/topic/96819/java-solution-8-lines-extendpalindrome*/
+    public int countSubstrings(String s) {
+        int count = 0;
+        for (int i = 0; i < s.length(); i++) {
+            count += extendPalindrome(s, i, i);//odd length
+            count += extendPalindrome(s, i, i+1);//even length
+        }
+        return count;
+    }
+
+    private int extendPalindrome(String s, int left, int right) {
+        int count = 0;
+        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
+            count++;
+            left--;
+            right++;
+        }
+        return count;
+    }
+}
