C++: O(n): Readable and modular


#1

#include
typedef vector vs;

/*
input: 000xyz
output: xyz
*/
string trim_start_zeros(string x){
int i=0;
while(x[i]==‘0’) i++;
return x.substr(i, x.length()-i);
}

/*
input: 23.1.002.00.4
output: [“23”, “1”, “2”, “”, “4”]
*/
vs strsplit(string x, char delim){
vs res;
string temp;
for(int i=0; i<x.length(); i++){
if(x[i]==delim){
res.push_back(trim_start_zeros(temp));
temp = “”;
continue;
}
temp += x[i];
}
res.push_back(trim_start_zeros(temp));
return res;
}

int compare_version(string ver_a, string ver_b){
if(ver_a.length() > ver_b.length())
return 1;
if(ver_a.length() < ver_b.length())
return -1;
return (ver_a > ver_b) ? 1 : (ver_a < ver_b ? -1 : 0);
}

/*
remove trailing empty versions
input: [“x”, “y”, “”, “”]
output: [“x”, “y”]
*/
vs remove_empty_version(vs versions){
while(versions[versions.size()-1] == “”) versions.pop_back();
return versions;
}

int Solution::compareVersion(string a, string b){
vs a_versions = remove_empty_version(strsplit(a, ‘.’));
vs b_versions = remove_empty_version(strsplit(b, ‘.’));
int common_size = min(a_versions.size(), b_versions.size());
int i=0;
while(i<common_size){
int res = compare_version(a_versions[i], b_versions[i]);
if(res!=0)
return res;
i++;
}
if(a_versions.size()>b_versions.size())
return 1;
if(a_versions.size()<b_versions.size())
return -1;
return 0;
}