Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, “A man, a plan, a canal: Panama” is a palindrome. “race a car” is not a palindrome. Note: Have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome.
Determine whether an integer is a palindrome. Do this without extra space. Could negative integers be palindromes? (ie, -1) If you are thinking of converting the integer to string, note the restriction of using extra space. You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case? There is a more generic way of solving this problem.
Solution
refer my solution to reverse integer.
reverse the number. If the number is the same as its reversed, then it must be a palindrome.
negative integers as non-palindromes.
Even thought this passed OJ, didn’t deal with overflow issues.
First, compare the first and last digit. If they are not the same, it must not be a palindrome. If they are the same, chop off one digit from both ends and continue until you have no digits left, which you conclude that it must be a palindrome.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
publicbooleanisPalindrome2(int x) {
if (x < 0) returnfalse;
int div = 1;
while (x / div >= 10) {
div *= 10;
}
while (x != 0) {
int l = x / div;
int r = x % 10;
if (l != r) returnfalse;
x = (x % div) / 10;
div /= 100;
}
returntrue;
}
Scramble String
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = “great”:
1
2
3
4
5
6
7
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
To scramble the string, we may choose any non-leaf node and swap its two children. For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.
1
2
3
4
5
6
7
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
We say that “rgeat” is a scrambled string of “great”. Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.
1
2
3
4
5
6
7
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
We say that “rgtae” is a scrambled string of “great”. Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
Iterative Solution
If string s1 and s2 are scramble strings, there must be a point(i) that breaks s1 to two parts s11, s12, and a point(l-i) that breaks s2 to two parts, s21, s22, and isScramble(s11, s21) && isScramble(s12, s22) is true, or isScramble(s11, s22) && isScramble(s12, s21) is true.
Cases to consider to avoid LTE:
If the lengths of two strings are different, they can’t be scramble.
If the characters in two strings are different, they can’t be scramble either.
System.out.println(" d "+Integer.toBinaryString(d) +" tmp "+tmp);
res=tmp+res;
d >>= 1;
System.out.println(" d: "+d+ " b "+Integer.toBinaryString(d));
}
System.out.println(res);
return res;
}
2) 1100->0011 1111->1111
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public String ReverseBinary(int d){
int n=Integer.toBinaryString(d).length();
StringBuffer sb=new StringBuffer();
System.out.println(" d "+d);
while(d!=0){
sb.append(d ^ 0x01);
System.out.println(" d "+d+" sb "+sb+ " "+0x01);
d >>= 1;
System.out.println(" d: "+d+ " b "+Integer.toBinaryString(d));
}
String s=sb.toString();
System.out.println(" s: "+s);
String res=Integer.valueOf(s, 2).toString();
return res;
}
Interleaving String
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. For example, Given: s1 = “aabcc”, s2 = “dbbca”, When s3 = “aadbbcbcac”, return true. When s3 = “aadbbbaccc”, return false.
Recursive Solution
Three pointers, four cases:
char at p3 equals to both p2, p1. either result could be true
char at p3 only equals to p2, increment these two pointers. If one of p1, p2 reached its length, just compare the rest substring
