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".
class Solution(object): def convert(self, s, numRows): """ :type s: str :type numRows: int :rtype: str """ rows = ["" for x in range(numRows)] count = 0 start = 0 end = numRows inc = 1 # while we dont run out of letters while count < len(s): # count from index 0 -> numRows -> numRows for i in range(start, end, inc): if count < len(s): rows[i] += s[count] count += 1 if inc == 1: inc = -1 start = numRows-2 end = 0 else: inc = 1 start = 0 end = numRows return "".join(rows) sol = Solution() s = "PAYPALISHIRING" numRows = 3 print sol.convert(s, numRows)This solution goes through the string once, using a loop that changes direction when it hits the number of rows. Then, this simply joins the separated rows of strings into one, which makes an O(n) complexity.
0 comments:
Post a Comment