LeetCode 解題紀錄 165. Compare Version Numbers

Compare Version Numbers - LeetCode

題目

給定兩個版本字串(包含版本號與改版 ex 1.23)，若左邊的版本較早回傳 -1，反之傳 1，相等的話回傳 0，改版本數字前的 0 可視為不存在(1.023 = 1.23)

限制

• 版本字串 1~500 個字元
• 字串只包含數字與小數點符號 ‘.’
• 每個數字都在整數的範圍類

觀察

• 可以根據改版分隔符號，把版本 次改版 次次改版的版本號分別取出，轉換成數字方便比較
• 版本字串的改版數目不一定相等，例如 1.2 與 1.2.31.5，將 1.2 補足為 1.2.0.0 就可以比較了

思路

• 先判斷最大版本數，好配置夠大的數字陣列
• 由左至右比對兩個數字陣列

Trial 1

• 呼叫 split() 函數會使用小數點符號來區分數字，注意要使用跳脫字元，避免被當成是是正規表示法裡的特殊字元
• 0012 這樣的字串，當使用Integer.valueOf()函數轉換時會自動被辨認成 12，不須額外處理前綴的 0 字元

結果

時間與空間複雜度為 O (m+n)，m 與 n 為版本/次版本個數

Trial 2

• 研究別人的寫法後，發現可以不需要暫存數字，直接比較

結果

時間與空間複雜度不變，程式碼變得精簡許多