zig-zag-conversion.dart (1678B)
1 //Return a string if it were to be placed in a matrix with a zig zag pattern 2 //and then returned read from left to right top to bottom. 3 //Ex. 4 //Input: 5 //ThisQuestionSucks | numRows = 3 6 //T q t s c 7 //hsusinuk 8 //i e o c 9 //Output: 10 //TQtSshsusinukieoc 11 //My solution simulates creating a zigzagged 2d array by 12 //creating the first array and filling it to the height. Then 13 //height -2 times moving to the side placing the character one 14 //higher each time. At the end the matrix is read and returned. 15 //The time complexity of this code is O(n) where n is the length of the 16 //string. 17 //Time: 860ms Beats: 6.17% 18 //Memory: 187.8MB Beats: 6.17% 19 20 class Solution { 21 String convert(String s, int numRows) { 22 List<List<String>> zigzag = []; 23 int placed = 0; 24 while(placed < s.length){ 25 zigzag.add([]); 26 for(int i = 0 ; i < numRows && placed < s.length; ++i){ 27 zigzag[zigzag.length - 1].add(s[placed]); 28 placed += 1; 29 } 30 for(int i = 0 ; i < numRows - 2 ; ++i){ 31 zigzag.add([]); 32 for(int x = 0 ; x < numRows - i - 2; ++x){ 33 zigzag[zigzag.length - 1].add(""); 34 } 35 if(placed < s.length){ 36 zigzag[zigzag.length - 1].add(s[placed]); 37 placed += 1; 38 } 39 else{ 40 break; 41 } 42 43 } 44 } 45 String ret_val = ""; 46 for(int x = 0 ; x < zigzag[0].length; ++x){ 47 for(int i = 0 ; i < zigzag.length ; ++i){ 48 if(zigzag[i].length - 1 >= x){ 49 ret_val += zigzag[i][x]; 50 } 51 } 52 } 53 54 return ret_val; 55 } 56 }