Sunday, September 15, 2013

Valid Palindrome

Q:
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.

A:

-----------------第三遍--------------------------

public class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        int i = 0, j = s.length() - 1;
        while (i < j) {
            // find i till it is a character
            while (i < j && !isAlphanumeric(s.charAt(i))) {
                i++;
            }
            // find j till it is a character
            while (j > i && !isAlphanumeric(s.charAt(j))) {
                j--;
            }
            if (i <= j && s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

    private boolean isAlphanumeric(char ch) {
        return (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9');
    }
}



错误: 
1: 忘了update i ,j

2: 没有注意是 alphanumeric
3: copy的时候, 把j  直接copy了i,没有发觉。
4: 在对比两个char是否相等的时候,忘了也要确保i<j

-----------------第二遍--------------------------
public class Solution {
    public boolean isPalindrome(String s) {
        StringBuffer buf = new StringBuffer();
        for(int i =0;i<s.length();i++){
            char ch = s.charAt(i);
            if( (ch>='A'&&ch<='Z' )|| (ch>='a'&&ch<='z')|| (ch>='0'&&ch<='9') )
                buf.append(ch);
        }
        s = buf.toString().toLowerCase();
        int i =0,j=s.length()-1;
        while(i<j){
            if(s.charAt(i) != s.charAt(j))
                return false;
            i++;
            j--;
        }
        return true;
    }
}

-----------------1 st -------------------
public class ValidPalindrome {
    public boolean isPalindrome(String s) {
        // check empty string or null object
        if (s.length() == 0 || s == null) {
            return true;
        }
        int n = s.length();
        int i = 0;
        int j = n - 1;
        char chI, chJ;
        while (i <= j) {
            // find the
            while (i < n && !isAlphanumeric(s.charAt(i))) {
                i++;
            }
            while (j >= 0 && !isAlphanumeric(s.charAt(j))) {
                j--;
            }
            if (i < n && j >= 0) {
                chI = s.charAt(i);
                chJ = s.charAt(j);
                if (chI >= 'A' && chI <= 'Z') {
                    chI = (char) (chI + 'a' - 'A');
                }
                if (chJ >= 'A' && chJ <= 'Z') {
                    chJ = (char) (chJ + 'a' - 'A');
                }
                if (chI != chJ) {
                    return false;
                }
                i++;
                j--;
            }
        }
        return true;
    }

    boolean isAlphanumeric(char ch) {
        if (ch >= 'A' && ch <= 'Z')
            return true;
        if (ch >= 'a' && ch <= 'z')
            return true;
        if (ch >= '0' && ch <= '9')
            return true;
        return false;
    }

}

 Mistakes:
1: 在check 一个string, 是否是palindrome 的时候, 这次,虽然记得update index, 但是,确把后一个j, 给顺手写成了 j++; (跟随前面的i++)

2: 即使是在Eclipse中, 不能随便用 代码完成, 这次, 就给搞出了,自己调用自己的问题了。哎~~~~~~~~ 死循环

3: 因为是linear的, 也不能随便增加遍数, 这次,就是又一次time limit exceed了。哎。------------------好吧, StringBuffer 不让用。 那就不用了。

4: 没有考虑 “  ” 的情况, 这样,会导致,i,j 越界 !!!!!!!!!!!!
5:  alphanumeric characters    是什么意思呢????  是字母加数字!!!!!!

Learned:
1: char 类型,要加到一个值的时候, 要加个类型转换。
 char ch = C;  //要转换成lower caes
ch = (char)(ch + ('a' - 'A'));

No comments:

Post a Comment