Valid Palindrome

Problem:

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.

Analysis:
答案里面是从两端到中间,而且剔除字符和空格没有用多余的function，真简洁。我的想法是从中间到两端。明显复杂一些。Anyway, 能自己写出来通过是好事。对自己的预期不能再低了，呵呵。
Solution:

1:  public static boolean isPalindrome(String s)  
2:       {  
3:            int j=0;  
4:            int k=0;  
5:            s=trimString(s.toLowerCase());  
6:            int mod=s.length()%2;  
7:            if(mod==0)  
8:            {  
9:                 j=s.length()/2-1;  
10:                 k=j+1;  
11:            }  
12:            else  
13:            {  
14:                 j=s.length()/2;  
15:                 k=j;  
16:            }  
17:            for(;j>=0;j--,k++)  
18:            {  
19:                 if(s.charAt(j)!= s.charAt(k))  
20:                      return false;  
21:            }  
22:            return true;  
23:       }  
24:       public static String trimString(String s)  
25:       {  
26:      StringBuilder sb= new StringBuilder();  
27:            for(char c: s.toCharArray())  
28:            {  
29:                 if((c>='a'&&c<='z')||(c>='0'&&c<='9') )  
30:                 {  
31:                      sb.append(c);  
32:                 }  
33:            }  
34:            return sb.toString();  
35:       }  

Implement strStr()

Problem:

Implement strStr().

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

Analysis:

这道题在leetcode String分类里算简单的。是因为暴力法很简单易懂。更高级的有Rabin-Karp algorithm, KMP algorithm 和 Boyer0 Moore algorigthm。以上都是出现在高级算法设计课的。暂时达不到那个高度。

Solution:

1:  public static int strStr(String haystack, String needle)  
2:       {  
3:            int hlen=haystack.length();  
4:            int nlen=needle.length();  
5:            if(haystack==null || needle==null || nlen<hlen)  
6:                 return -1;  
7:            boolean isSub=true;  
8:            for(int i=0;i<hlen-nlen;i++)  
9:            {  
10:          isSub=true;          
11:             for(int j=0;j<nlen;j++)  
12:             {  
13:                  if(haystack.charAt(i+j)!=needle.charAt(j))  
14:               {  
15:                   isSub=false;  
16:                   break;  
17:               }  
18:             }  
19:             if(isSub)  
20:                 return i;   
21:            }  
22:            return -1;  
23:       }