Compare Version Numbers Editorial

Practice Problem Link: Compare Version Numbers | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given two version numbers, compare them. 

A version number consists of one or more revisions connected by a dot. Each revision consists of digits and may contain leading zeroes. Each revision consists of at least one digit. 

Revisions are 0-indexed from left to right. 

To compare two versions, compare revisions in the left-to-right order. Revisions are compared using their integer value ignoring any leading zeroes.

Approach

Since there are multiple dots in the given versions, comparing them directly is not possible. Therefore to compare the two versions we have to compare the substrings which are partitioned by dots.

• Traverse both the strings simultaneously and store each string’s corresponding substring (excluding the leading zeroes).
• If the length of the substring of s1 is greater than the length of the substring of s2, return 1
• Else if the length of the substring of s1 is less than then the length of the substring of s2, return -1.
• If both the substrings have equal length:
  • compare the elements of both the substrings
  • if at any point the value of two corresponding sections differs then return the answer accordingly.
• If both the substrings are identical, move to the next substrings.
• Return 0 as the default case.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

int compareVersion(string version1, string version2) {
   string subVersion1 = "", subVersion2 = "";
   int i = 0, j = 0;
   while (i < version1.size() || j < version2.size()) {
       while (i < version1.size() && version1[i] == '0') {
           i++;
       }
       while (i < version1.size() && version1[i] != '.') {
           subVersion1 += version1[i];
           i++;
       }
       while (j < version2.size() && version2[j] == '0') {
           j++;
       }
       while (j < version2.size() && version2[j] != '.') {
           subVersion2 += version2[j];
           j++;
       }
       if (subVersion1.size() > subVersion2.size()) {
           return 1;
       } else if (subVersion1.size() < subVersion2.size()) {
           return -1;
       }
       for (int k = 0; k < subVersion1.size(); k++) {
           if (subVersion1[k] > subVersion2[k]) {
               return 1;
           } else if (subVersion1[k] < subVersion2[k]) {
               return -1;
           }
       }
       subVersion1 = "";
       subVersion2 = "";
       i++;
       j++;
   }
   return 0;
}

Java

class Solution {
   int compareVersion(String version1, String version2) {
       String subVersion1 = "", subVersion2 = "";
       int i = 0, j = 0;
       while (i < version1.length() || j < version2.length()) {
           while (i < version1.length() && version1.charAt(i) == '0') {
               i++;
           }
           while (i < version1.length() && version1.charAt(i) != '.') {
               subVersion1 += version1.charAt(i);
               i++;
           }
           while (j < version2.length() && version2.charAt(j) == '0') {
               j++;
           }
           while (j < version2.length() && version2.charAt(j) != '.') {
               subVersion2 += version2.charAt(j);
               j++;
           }
           if (subVersion1.length() > subVersion2.length()) {
               return 1;
           } else if (subVersion1.length() < subVersion2.length()) {
               return -1;
           }
           for (int k = 0; k < subVersion1.length(); k++) {
               if (subVersion1.charAt(k) > subVersion2.charAt(k)) {
                   return 1;
               } else if (subVersion1.charAt(k) < subVersion2.charAt(k)) {
                   return -1;
               }
           }
           subVersion1 = "";
           subVersion2 = "";
           i++;
           j++;
       }
       return 0;
   }
}