add-binary.dart (1707B)
1 //Add two strings together that are "binary" strings 2 //with ones and zeroes. I did this by assigning them to a reversed 3 //list and then going through them one value at a time carrying the remainders. 4 //I another approach is to use binary to decimal conversion, but 5 //the problem is that in leetcode it says b.length<=10^4 which means 6 //the input could be larger than 64 bits thus can't be stored in an int. 7 //The worst case time complexity of this is O(n^2). 8 //Runtime: 270ms Beats: 84.31% 9 //Memory: 142.5MB Beats: 74.51% 10 11 void main(){ 12 Solution sol = new Solution(); 13 print(sol.addBinary("010110101011", "1010111010101")); 14 15 } 16 17 class Solution { 18 19 String addBinary(String a, String b) { 20 List<String> long; 21 List<String> short; 22 if(a.length > b.length){ 23 long = a.split(""); 24 short = b.split(""); 25 } 26 else{ 27 long = b.split(""); 28 short = a.split(""); 29 } 30 short = short.reversed.toList(); 31 long = long.reversed.toList(); 32 for(int i = 0 ; i < short.length ; ++i){ 33 int carry = 0; 34 if(short[i] == '0'){ 35 continue; 36 } 37 if(long[i] == '1'){ 38 long[i] = '0'; 39 carry = 1; 40 } 41 else{ 42 long[i] = '1'; 43 continue; 44 } 45 int next_val = i + 1; 46 while(carry != 0){ 47 if(next_val >= long.length){ 48 long.add('0'); 49 continue; 50 } 51 if(long[next_val] == '1'){ 52 long[next_val] = '0'; 53 } 54 else{ 55 long[next_val] = '1'; 56 carry = 0; 57 } 58 next_val += 1; 59 60 } 61 } 62 return long.reversed.join(''); 63 } 64 }