Day 4 Interview

1. Longest Palindromic String

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Approach:

1. Naive Approach

Naively, we can simply examine every substring and check if it is palindromic. The time complexity is O(n^3). If this is submitted to LeetCode onlinejudge, an error message will be returned – “Time Limit Exceeded”. Therefore, this approach is just a start, we need better algorithm.

public static String longestPalindrome1(String s) {
 
	int maxPalinLength = 0;
	String longestPalindrome = null;
	int length = s.length();
 
	// check all possible sub strings
	for (int i = 0; i < length; i++) {
		for (int j = i + 1; j < length; j++) {
			int len = j - i;
			String curr = s.substring(i, j + 1);
			if (isPalindrome(curr)) {
				if (len > maxPalinLength) {
					longestPalindrome = curr;
					maxPalinLength = len;
				}
			}
		}
	}
 
	return longestPalindrome;
}
 
public static boolean isPalindrome(String s) {
 
	for (int i = 0; i < s.length() - 1; i++) {
		if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
			return false;
		}
	}
 
	return true;
}

2. Dynamic Programming

Let s be the input string, i and j are two indices of the string.

Define a 2-dimension array “table” and let table[i][j] denote whether substring from i to j is palindrome.

Start condition:

table[i][i] == 1;
table[i][i+1] == 1  => s.charAt(i) == s.charAt(i+1) 

Changing condition:

table[i][j] == 1 => table[i+1][j-1] == 1 && s.charAt(i) == s.charAt(j)

Time O(n^2) Space O(n^2)

public static String longestPalindrome2(String s) {
	if (s == null)
		return null;
 
	if(s.length() <=1)
		return s;
 
	int maxLen = 0;
	String longestStr = null;
 
	int length = s.length();
 
	int[][] table = new int[length][length];
 
	//every single letter is palindrome
	for (int i = 0; i < length; i++) {
		table[i][i] = 1;
	}
	printTable(table);
 
	//e.g. bcba
	//two consecutive same letters are palindrome
	for (int i = 0; i <= length - 2; i++) {
		if (s.charAt(i) == s.charAt(i + 1)){
			table[i][i + 1] = 1;
			longestStr = s.substring(i, i + 2);
		}	
	}
	printTable(table);
	//condition for calculate whole table
	for (int l = 3; l <= length; l++) {
		for (int i = 0; i <= length-l; i++) {
			int j = i + l - 1;
			if (s.charAt(i) == s.charAt(j)) {
				table[i][j] = table[i + 1][j - 1];
				if (table[i][j] == 1 && l > maxLen)
					longestStr = s.substring(i, j + 1);
			} else {
				table[i][j] = 0;
			}
			printTable(table);
		}
	}
 
	return longestStr;
}
public static void printTable(int[][] x){
	for(int [] y : x){
		for(int z: y){
			System.out.print(z + " ");
		}
		System.out.println();
	}
	System.out.println("------");
}

Given an input, we can use printTable method to examine the table after each iteration. For example, if input string is “dabcba”, the final matrix would be the following:

1 0 0 0 0 0 
0 1 0 0 0 1 
0 0 1 0 1 0 
0 0 0 1 0 0 
0 0 0 0 1 0 
0 0 0 0 0 1 

From the table, we can clear see that the longest string is in cell table[1][5].

3. Simple Algorithm

Time O(n^2), Space O(1)

public String longestPalindrome(String s) {
	if (s.isEmpty()) {
		return null;
	}
 
	if (s.length() == 1) {
		return s;
	}
 
	String longest = s.substring(0, 1);
	for (int i = 0; i < s.length(); i++) {
		// get longest palindrome with center of i
		String tmp = helper(s, i, i);
		if (tmp.length() > longest.length()) {
			longest = tmp;
		}
 
		// get longest palindrome with center of i, i+1
		tmp = helper(s, i, i + 1);
		if (tmp.length() > longest.length()) {
			longest = tmp;
		}
	}
 
	return longest;
}
 
// Given a center, either one letter or two letter, 
// Find longest palindrome
public String helper(String s, int begin, int end) {
	while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
		begin--;
		end++;
	}
	return s.substring(begin + 1, end);
}

4. Manacher’s Algorithm

Manacher’s algorithm is much more complicated to figure out, even though it will bring benefit of time complexity of O(n).

Since it is not typical, there is no need to waste time on that.

2. ZigZag conversation

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Approach: TO DO LATER!

 

3. Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Approach:

 

 

 
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