LeetCode 6. ZigZag Conversion

LeetCode problem No.6.

No.5 is here.

modalsoul.hatenablog.com

6. ZigZag Conversion

https://leetcode.com/problems/zigzag-conversion/

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

Example1

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example2

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"

Code 1

object Solution {
  def convert(s: String, numRows: Int): String = {
    if(numRows == 1) return s
    val converted:Array[String] = (0 until numRows).map(_ => "").toArray
    for {
      i <- 0 until s.length
    } {
      if(i%(numRows*2-2) < numRows) {
        converted(i%(numRows*2-2)) = converted(i%(numRows*2-2)) + s(i)
      } else {
        val index = numRows - i%(numRows-1) - 1
        converted(index) = converted(index) + s(i)
      }
    }
    converted.fold("")((z,n) => z + n)
  }
}

Methods

• Prepare numRows strings.
• Read given string and append each character to prepared strings.
  • Characters located indexes i in given string,
    • If i % (numRows*2-2) < numRows, characters are vertically aligned.
      • Characters will locate i % (numRows*2-2) row.
    • Else, characters are the only character in each column.
      • Characters will locate numRows - i%(numRows-1) - 1 row.
• Concatenate all strings.

Result

Runtime: 624 ms, faster than 12.20% of Scala online submissions for ZigZag Conversion. Memory Usage: 57.8 MB, less than 100.00% of Scala online submissions for ZigZag Conversion.

Code 2

object Solution {
  def convert(s: String, numRows: Int): String = {
    if(numRows == 1) return s
    val converted:Array[String] = (0 until numRows).map(_ => "").toArray
    for {
      i <- 0 until s.length
    } {
      if(i%(numRows*2-2) < numRows) {
        converted(i%(numRows*2-2)) = converted(i%(numRows*2-2)) + s(i)
      } else {
        val index = numRows - i%(numRows-1) - 1
        converted(index) = converted(index) + s(i)
      }
    }
    converted.mkString
  }
}

Methods

• Use mkString instead of fold.

Result

Runtime: 588 ms, faster than 14.63% of Scala online submissions for ZigZag Conversion. Memory Usage: 57.6 MB, less than 100.00% of Scala online submissions for ZigZag Conversion.