ZigZag Conversion, Leetcode 解题笔记

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”.

这题就是找规律,利用一个2D array存储每一个字符在zigzag中的位置,然后打印。因为没办法确定2D array的长度,这里我用了一个笨办法,直接定义为最长的长度,即s.length()。事实证明这种方法不能通过,因为利用了很多多余的空间超时了,所以如果想通过就不能用array,可以用string或arraylist来动态改变存储长度,以至于不浪费空间。

我的code,用eclipse验证正确,但是对于超长string超时:

public class Solution {
    public String convert(String s, int nRows) {
        char[] ret = new char[s.length()];
        char[][] store = new char[s.length()][s.length()];

        int row = 0;
        int col = 0;
        int flag = 0; //check if the current position is at boundary
        if(nRows == 1) return s;

        for(int i = 0; i < s.length(); i++){
            store[row][col] = s.charAt(i);
            if(flag == 0 && row < nRows-1){
                row++;
            }
            else if(flag == 0 && row == nRows-1){
                row--;
                col++;
                flag = 1;
            }
            else if(flag == 1 && row > 0){
                row--;
                col++;
            }
            else if(flag == 1 && row == 0){
                row++;
                flag = 0;
            }
            else{}
        }
        
        //convert 2D array to string
        int index = 0;
        for(int i = 0; i < s.length(); i++){
            for(int j = 0; j < s.length(); j++){
                if(store[i][j] != '\u0000'){ //check if the char is 'null'
                    ret[index] = store[i][j];
                    index++;
                }
            }
        }
        return ret.toString();
    }
}

值得注意的是Java在初始化char array时的默认值是’\u0000’,意为空。

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