Shortest Palindrome/Implement strStr()

Leave a comment

February 13, 2017 by oneOokay

Shortest Palindrome: 找到prefix中最长的palindrome

Implement strStr():找到在heystack中第一次完整出现的needle在heystack中的index


Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".


找到s的prefix中最长的Palindrome,然后把剩下的substring翻转之后放到s的前面所组成的string,就是满足条件的shortest Palindrome.

这里用了3个指针的方法来找,我觉得还挺好可以做个模板的.

  • StringBuilder sb = new StringBuilder(str);
  • sb.reverse().toString();
  • StringBuilder vs StringBuffer:
    • StringBuilder 是 NOT Synchronized.更快
    • StringBuffer是Synchronized.更慢
    • 其他都一样.
public String shortestPalindrome(String s) {
 char[] c = s.toCharArray();
 int i = 0;
 int end = s.length() - 1;
 int j = end;
 while (i < j){
 if (c[i] == c[j]){
 i ++;
 j --;
 }else {
 i = 0;
 end --;
 j = end;
 }
 }
 return (new StringBuilder(s.substring(end + 1, s.length()))).reverse().toString() + s;
 }

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.


首先这个可以用前面的那个3个指针的方法.

然后还有一个更加elegant的方法,也算是一个基础想法/算法把:

needle的长度是固定的

  • 外层i loop haystack从0到haystack.length() – needle.length()
  • 内层j loop needle: j位置为needle char的位置; i+j的位置为haystack char的位置
public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        for (int i = 0; i <= haystack.length() - needle.length(); i ++){
            for (int j = 0; j < needle.length() && haystack.charAt(i + j) == needle.charAt(j); j ++){
                if (j == needle.length() - 1) return i;
            }
        }
        return -1;
    }

3个指针

public int strStr(String haystack, String needle) {
 if (needle.length() == 0) return 0;
 int p1 = 0;
 int p2 = 0;
 int start = 0;
 while (p1 < haystack.length()){
 if (haystack.charAt(p1) == needle.charAt(p2)){
 p1 ++;
 p2 ++;
 if (p2 == needle.length()) return start;
 }else {
 p2 = 0;
 start ++;
 p1 = start;
 }
 }
 return -1;
 } 
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: