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