Leetcode --- ZigZag Conversion(Medium)
===

## Description

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"

Suppose **the String is "ABCDEFG"** and **numRows equals 3**,the answer will be :

    A        E
    B    D   F
    C        G

ruturn answer's string is row1,row2,...,row n => AEBDFCG

Another supposition has **the same String** ,**but numRows equaling 4**,the answer is gonna be:

    A            G
    B        F
    C    E
    D

return AGBFCED

### Examples

* Ex1:
**Input**: s = "PAYPALISHIRING", numRows = 4
**Output**: "PINALSIGYAHRPI"
**Explanation**:
P I N
A L S I G
Y A H R
P I
* Ex2:
**Input**: s = "A", numRows = 1
**Output**: "A"

### Constraints

* 1 <= s.length <= 1000
* s consists of English letters (lower-case and upper-case), ',' and '.'.
* 1 <= numRows <= 1000

## Solutions

* ==**Solution 1:**==

舉幾個例子:

n=3
    A        E
    B    D   F
    C        G
    -----------
n=4
    A            G
    B        F
    C    E
    D

若要把整個問題分割成小問題的話,可以切成n+(n-2)為一組,n為從第1列到第n列,n-2為從最後一列爬回去,所以2n-2為小問題的字串長度

小問題解:
建立最多為n的bucket,把string丟到對應的bucket中且有先後順序,
例如n=3=>3個bucket,分別為row 0,row 1,row 2,
也就是說
A ->bucket 0 ,
B ->bucket 1 ,
C ->bucket 2 ,
D ->bucket 1 ......

所有小問題且依序處理後,依序輸出bucket 0 , bucket 1 .... 即為解.

!

### Implentment code

class Solution 
{
    public String convert(String s, int numRows) 
    {
        ListNode[] buf = new ListNode[numRows];
        ListNode[] head = new ListNode[numRows];
        for(int i =0;i<numRows;i++)
        {
            buf[i] = new ListNode('@');
            head[i] = buf[i];
        }
        int WholeStringPos=0;
        int NegativeAhead=0;
        boolean flag =false;
        while(WholeStringPos<s.length())
        {
            if(numRows ==1)
                return s;
            int PositiveAhead = WholeStringPos % (2*numRows-2);
            
            if(PositiveAhead==0)
            {
                NegativeAhead=0;
                flag=false;
            }
            while(!(buf[PositiveAhead + NegativeAhead].val == '@') )
            {
                buf[PositiveAhead + NegativeAhead].next = new ListNode('@');
                buf[PositiveAhead + NegativeAhead] = buf[PositiveAhead+NegativeAhead].next;
            }
            
            buf[PositiveAhead + NegativeAhead].val = s.charAt(WholeStringPos);
          
            if(PositiveAhead == numRows-1)
                flag =true;
            if(flag ==true)
                NegativeAhead-=2;
            WholeStringPos++;
        }
        String ans =new String();
        for(int p=0;p<numRows;p++)
        {
            while(!(head[p].val =='@'))
            {
                ans += head[p].val;
                head[p] = head[p].next;
                if(head[p] == null)
                    break;
            }
        }
        return ans;
    }
      
}
class ListNode
{
    char val ;
    ListNode next;
    public ListNode()
    {
        this.val ='@';
        this.next = null;
    }
    public ListNode(char val)
    {
        this.val = val ;
        this.next =null;
    }
    public ListNode(char val,ListNode next)
    {
        this.val = val ;
        this.next =next;
    }
}

* variable : PositiveAhead , NegativeAhead:
PositiveAhead為Subproblem往下爬,NegativeAhead為往上爬(上圖綠色線),當PositiveAhead=numRows才開始往上爬(boolean flag 控制)

* 使用Linked List 把屬於bucket 0之char串起來,bucket 1亦是 ... ,bucket n 亦是

### Submissions on Leetcode
Runtime: **15 ms, faster than 26.01%** of Java online submissions for ZigZag Conversion.
Memory Usage: **39.4 MB, less than 77.17%** of Java online submissions for ZigZag Conversion.

### Complexity Analysis

主程式部分把整個問題切割成每一個子問題最多為2numRows-2個字元,若採分散處理可以達
==O(2*numRows-2) = O(numRows)==
但此程式必無分散 => ==O(s.length())==

輸出部分要從linked list 從頭跑到尾,最差狀況發生再所有都擠在同一個 =>
==O(s.length())==

所以整個為 ==O(s.length()) + O(s.length()) = O(s.length())==

---

* ==**Solution 2**==
與Solution 1 概念相同,每個row去解出答案,但用StringBuilder解決

### Implement code

class Solution 
{
    public String convert(String s, int numRows) {
    
        if(numRows ==1)
            return s;
        List<StringBuilder> EachRows = new ArrayList<>();
        for(int i =0 ; i<Math.min(s.length(),numRows);i++)
            EachRows.add(new StringBuilder());
        boolean flag =false;
        for(int i =0,NOrow=0;i<s.length();i++)
        {
            EachRows.get(NOrow).append(s.charAt(i));
            if(NOrow == 0 || NOrow == numRows-1)
                flag = !flag;
            NOrow += flag ? 1 : -1; 
        }
        StringBuilder ans = new StringBuilder();
        
        for(StringBuilder row : EachRows)
            ans.append(row);
        
        return ans.toString();
        
    }
}

line 8 : crate所需要的list數量,每一子串都是StringBuilder
line 13: get()得到要插在某個子串
line 14~17:控制現在要插入子串的位子是往下還是往上(index)

### Time Complexity
==O(s.length())==

### Submission on leetcode

Runtime:**5 ms, faster than 76.72%** of Java online submissions for ZigZag Conversion.
Memory Usage: **39.7 MB, less than 53.86%** of Java online submissions for ZigZag Conversion.

比起solution 1 有明顯速度提升

---

* ==Solution 3:==
另一種想法為計算出**同一列中下一個字元出現的位置**,根據例子來找規則:

n=3
    A(0)        E(4)
    B(1)  D(3)  F(5)
    C(2)        G(6)
    -----------
n=4
    A(0)             G(6)
    B(1)        F(5) H(7)
    C(2)   E(4)      I(8)
    D(3)             J(9)

用兩個變數來描述位置 :
* TotalRows : 總共的列數,即input numRows
* CurrentRows : 以目前為最高層,剩下的列數,ex: n=4 , b的CurrentRows =3,c的CurrentRows =2 ...

可觀察出第一列與最後一列為相同的special case:

* row 0 ,TotalRows-1規則 : (CurrentRow =4)
走過TotalRows+(TotalRows-2),TotalRows為直線往下,TotalRows-2為往右上 : 兩點距離 ==2TotalRows-2==
* Otherwise 規則:
取E(4),I(8),TotalRows=4 , CurrentRows =2
E的位置在: (TotalRows-CurrentRows )+( 2CurrentRows-2) ... 直行中有多少字元在目前row之上 + 以目前row為最高層row之下一個位子 =**TotalRows +CurrentRows -2**
check: 4-2 + 2* 2-2 = 4(V)
I的位置在: 2TotalRows-2 + (TotalRows - CurrentRows) ... 走過上一個 + 目前行的位子
= **3TotalRows -CurrentRows -2**
check : 3* 4 - 2 -2 =8(V)

**總共距離** : (3TotalRows -CurrentRows -2 ) - (TotalRows +CurrentRows -2) = 2TotalRows-2CurrentRows = ==2(TotalRows-CurrentRows)==

**第二個核心想法為**:從第一列找完,找第二列時看成把第一列抽掉,即n-1的解,可以找到下一個字元,在帶入Otherwise規則,找到下下一個.....,第三列亦是n-2的解...

### Implement code (**The neat code**)

class Solution 
{
    public String convert(String s, int numRows) {
    
        StringBuilder ans = new StringBuilder();
        if(numRows ==1 )
            return s;
            
        for(int CurrentRow = numRows ,start=0; CurrentRow>=1;)
        {
            helper(start,s,ans,CurrentRow,numRows);
            CurrentRow --;
            start++;
        }
        return ans.toString();
    }
    private void helper(int start,String s,StringBuilder ans,int CurrentRow,int TotalRows)
    {
        boolean change =false;
        for(int i =start ;i<s.length();)
        {
            if(change ==false && CurrentRow !=1)
            {
                ans.append(s.charAt(i));
                i += 2*CurrentRow-2;
            }
            else if(TotalRows != CurrentRow)
            {
                ans.append(s.charAt(i));
                i += 2*(TotalRows-CurrentRow);
            }
            change =!change;
        }
    }
}

* for loop statement:
初始值可以宣告無限多個,但必須是同一個型態(int,String,boolean ...),沒有增減值時等同於while loop,而且變數將會宣告在for loop的區域內,可節省一點點的記憶體空間
**line 9與line 20均用到此技巧**

* helper function:
此方法以列為單位完成往下找解,
for loop:start為初始位置,i起始為start且下一個位置有兩個選項去找到下一個同一列的字元,
第一個位移為2n-2中間沒有其他字元在同列,第二個位移則2(總列-現在列),找到在一個循環中的字元,而if的另一個條件均是對邊緣資料做處理.

* Main 的for:
以列為單位找解,假設n=3;找到起始位置為0且第3列的所有解後,起始位置為1且第二列的所有解.....
最後即為解

### Submissions on leetcode

Runtime: **2 ms, faster than 99.97%** of Java online submissions for ZigZag Conversion.
Memory Usage: **39.3 MB, less than 83.25%** of Java online submissions for ZigZag Conversion.

###### tags: `Leetcode` `Medium` `Divide and Conquer` `String`