|
| 1 | +##Leetcode Blog Version |
1 | 2 |
|
2 | | -##TODO |
3 | | -*writedown thinking |
| 3 | +Here is the[Leetcode Blog Version](http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html). |
| 4 | +This is a classic problem. Iwritemy first leetcode accepted version based on that. |
4 | 5 |
|
| 6 | + |
| 7 | +##My own words version |
| 8 | + |
| 9 | +Brute force + isPalindromic will run out of time. |
| 10 | + |
| 11 | +###Recursive |
| 12 | + |
| 13 | +*`length 1 substring`: all are palindromic |
| 14 | +*`length 2 substring`: only if two char are same |
| 15 | + |
| 16 | +What if`length 3` |
| 17 | + |
| 18 | +``` |
| 19 | +
|
| 20 | +length 3 = length 1 + two char |
| 21 | +
|
| 22 | +0 1 2 3 4 |
| 23 | +a b c b a |
| 24 | ++ ^ |
| 25 | +| | |
| 26 | ++---+ |
| 27 | +
|
| 28 | +
|
| 29 | +0 1 2 4 4 |
| 30 | +a b c b a |
| 31 | + + ^ |
| 32 | + | | |
| 33 | + +---+ |
| 34 | +
|
| 35 | +``` |
| 36 | + |
| 37 | +*`length n` = inner`length n - 2` is palindromic AND (first char == last char) |
| 38 | + |
| 39 | + |
| 40 | +###Store`length n` into`P[lenght n][start index]` |
| 41 | + |
| 42 | +*`P[1][3] = true` means that the substring starts from index 3 and 1 char long is palindromic. |
| 43 | +*`P[5][2] = true` means that the substring starts from index 2 and 5 char long is NOT palindromic. |
| 44 | + |
| 45 | + |
| 46 | +a matrix for`abcba` |
| 47 | + |
| 48 | +``` |
| 49 | +
|
| 50 | + 0 1 2 3 4 |
| 51 | + a b c b a |
| 52 | +1 1 1 1 1 1 |
| 53 | +2 0 0 0 0 - |
| 54 | +3 0 1 0 - - |
| 55 | +4 0 0 - - - |
| 56 | +5 1 - - - - |
| 57 | +^ |
| 58 | +l |
| 59 | +e |
| 60 | +n |
| 61 | +
|
| 62 | +``` |
| 63 | + |
| 64 | +With the matrix, we can fill up the martix by`P[len][i] = P[len -2][i + 1] && S[i] == S[i + len -1]`. |
| 65 | + |
| 66 | + |
| 67 | +Note: the`length 0` is useless, so just using`P[len - 1]` for`len`. |