O(n) Solution in Java, only one time traversal.


  • 0
    Z

    O(n) Solution in Java, only one time traversal.

       public class Solution {
            public String convert(String s, int nRows) {
                if (nRows<=1) return s;
                StringBuilder sb = new StringBuilder();
                int step = 2 *nRows - 2;
                for(int i=0; i<nRows; i++)
                {
                    for(int j=i; j<s.length(); j+=step)
                    {
                        sb.append(s.charAt(j));
                        
                        int thisSubIndex = j%step;
                        int nextSubIndex = step-thisSubIndex;
                        if (nextSubIndex!=step && nextSubIndex!=thisSubIndex)
                        {
                            int nextTrueIndex = j+nextSubIndex-thisSubIndex;
                            if (nextTrueIndex<s.length())
                            {
                                sb.append(s.charAt(nextTrueIndex));
                            }
                        }
                    }
                }
                return sb.toString();
            }
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.