Created
July 7, 2016 11:47
-
-
Save zzt93/95cbddb6e6db41c0b49114ceb09c41f6 to your computer and use it in GitHub Desktop.
A solution for longest palindromic problem and used to learn profiling
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package interview.leetcode; | |
import competition.utility.MyIn; | |
import java.util.ArrayList; | |
/** | |
* Created by zzt on 7/6/16. | |
* <p> | |
* <h3></h3> | |
* | |
* @see WrongLongestPalindromic | |
* @see WrongLongestSub | |
*/ | |
public class LongestPalindromic { | |
private static class PalindromicCenter { | |
// not include '.' | |
private boolean canExtend; | |
private int maxLen; | |
private int i; | |
PalindromicCenter(int maxLen, int i) { | |
this.canExtend = true; | |
this.maxLen = maxLen; | |
this.i = i; | |
} | |
} | |
/** | |
* <h3>Dynamic equation</h3> | |
* longestCenter[n-1] + 2/1 = longestCenter[n] if new char is the same with | |
* symmetric char | |
* | |
* @return if multiple string with same max len, return the first string | |
*/ | |
public static String lpDynamic(String string) { | |
if (string.isEmpty()) { | |
return ""; | |
} | |
if (string.length() == 1) { | |
return string; | |
} | |
int len = string.length(); | |
final ArrayList<PalindromicCenter> centers = new ArrayList<>(len * 2 - 1); | |
final char[] toCharArray = string.toCharArray(); | |
{ | |
int j = 0; | |
for (int in = 0; in < toCharArray.length - 1; in++) { | |
centers.add(new PalindromicCenter(1, j++)); | |
centers.add(new PalindromicCenter(0, j++)); | |
} | |
centers.add(new PalindromicCenter(1, j)); | |
} | |
final int size = centers.size(); | |
int maxCenterI = 0; | |
int max = 0; | |
boolean canExtend; | |
do { | |
canExtend = false; | |
for (int i = 0; i < size; i++) { | |
final PalindromicCenter center = centers.get(i); | |
if (center.canExtend && extendCenter(center, i, toCharArray, len)) { | |
canExtend = true; | |
if (center.maxLen > max) { | |
max = center.maxLen; | |
maxCenterI = i; | |
} | |
} else { | |
center.canExtend = false; | |
} | |
} | |
} while (canExtend); | |
final PalindromicCenter first = centers.get(maxCenterI); | |
StringBuilder sb = new StringBuilder(first.maxLen); | |
int dis = disToCenter(first); | |
int start = noDotArrayIndex(first.i - dis) + 1; | |
int end = noDotArrayIndex(first.i + dis); | |
while (start < end) { | |
sb.append(toCharArray[start]); | |
start++; | |
} | |
return sb.toString(); | |
} | |
private static int disToCenter(PalindromicCenter first) { | |
return first.maxLen + 1; | |
} | |
private static boolean extendCenter(PalindromicCenter center, int centerI, char[] chars, int end) { | |
int dis = disToCenter(center); | |
int left = noDotArrayIndex(centerI - dis); | |
int right = noDotArrayIndex(centerI + dis); | |
if (left >= 0 && right < end) { | |
if (chars[left] == chars[right]) { | |
center.maxLen += 2; | |
return true; | |
} | |
} | |
return false; | |
} | |
/** | |
* @param i Index in extended array which has '.' in it | |
* | |
* @return the index of a character in the original array | |
*/ | |
private static int noDotArrayIndex(int i) { | |
if ((i & 1) == 1) { | |
assert false; | |
} | |
return i / 2; | |
} | |
public static void main(String[] args) { | |
MyIn in = new MyIn(); | |
// in.next(); | |
final WrongLongestSub wrongLongestSub = new WrongLongestSub(); | |
output(wrongLongestSub, "ccc"); | |
output(wrongLongestSub, "cccc"); | |
output(wrongLongestSub, "ccccc"); | |
output(wrongLongestSub, "abcbcb"); | |
output(wrongLongestSub, "abcbac"); | |
output(wrongLongestSub, "aaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeeeffffffffffgggggggggghhhhhhhhhhiiiiiiiiiijjjjjjjjjjkkkkkkkkkkllllllllllmmmmmmmmmmnnnnnnnnnnooooooooooppppppppppqqqqqqqqqqrrrrrrrrrrssssssssssttttttttttuuuuuuuuuuvvvvvvvvvvwwwwwwwwwwxxxxxxxxxxyyyyyyyyyyzzzzzzzzzzyyyyyyyyyyxxxxxxxxxxwwwwwwwwwwvvvvvvvvvvuuuuuuuuuuttttttttttssssssssssrrrrrrrrrrqqqqqqqqqqppppppppppoooooooooonnnnnnnnnnmmmmmmmmmmllllllllllkkkkkkkkkkjjjjjjjjjjiiiiiiiiiihhhhhhhhhhggggggggggffffffffffeeeeeeeeeeddddddddddccccccccccbbbbbbbbbbaaaaaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeeeffffffffffgggggggggghhhhhhhhhhiiiiiiiiiijjjjjjjjjjkkkkkkkkkkllllllllllmmmmmmmmmmnnnnnnnnnnooooooooooppppppppppqqqqqqqqqqrrrrrrrrrrssssssssssttttttttttuuuuuuuuuuvvvvvvvvvvwwwwwwwwwwxxxxxxxxxxyyyyyyyyyyzzzzzzzzzzyyyyyyyyyyxxxxxxxxxxwwwwwwwwwwvvvvvvvvvvuuuuuuuuuuttttttttttssssssssssrrrrrrrrrrqqqqqqqqqqppppppppppoooooooooonnnnnnnnnnmmmmmmmmmmllllllllllkkkkkkkkkkjjjjjjjjjjiiiiiiiiiihhhhhhhhhhggggggggggffffffffffeeeeeeeeeeddddddddddccccccccccbbbbbbbbbbaaaa"); | |
// in.next(); | |
// for (int i = 0; i < 10; i++) { | |
// final String s = RandomStr.sameSeed(10); | |
// output(wrongLongestSub, s); | |
// } | |
} | |
private static void output(WrongLongestSub wrongLongestSub, String s) { | |
System.out.print(s + ": "); | |
System.out.print(lpDynamic(s) + ": "); | |
System.out.println(wrongLongestSub.longestPalindrome(s)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment