筆記 - ASCII code 應用於字串檢查與轉換

Posted on In

在做 Leetcode 時夥伴說檢查 string 的字符是否落在 ASCII 的 0 - 9 （數字字符）編碼中，發現在檢查 string character 有好多方法。

Character Encoding

簡單來說，計算機剛開始發展的時候，美國對英語字符與二進位關係做了一套編碼原則，就是 ASCII (American Standard Code for Information Interchange，美國標準資訊交換碼），使用七位二進位共定義 128 個字符的編碼規則。

wiki

Image

之後隨著計算機在其他國家普及，各國也發展了自己語言的編碼方式，但編碼系統不同也造成交流困難，所以就發展了 Unicode 國際標準字符集。常見有 UTF-8，UTF-16 字符編碼規則， UTF (Unicode Transformation Format) 意思是 Unicode 轉換格式，後面的數字表至少使用多少個 bit 來存儲字符, 比如：UTF-8 最少需要 8 bit (= 1 byte) 來儲存。不同編碼規則都能獲得對應的 Unicode 碼，所以是能互相轉換的。另外 UTF-8 相容 ASCII 。

以下都看不懂了，大概先知道這樣。

參考文章

Leetcode 8. String to Integer (atoi)

總之緣起是這一題Leetcode 8.，題目要把 string 轉成在 32-bit 含正負號的整數。

依照題目需求，把 string 讀入之後，從 index = 0 開始先去除前頭的空白，然後讀到正號貨負號的話就用將 sign 值存成 1 或 -1。

接下來是要確認每個 character 是 數字 digits 而不是文字或其他符號。

(1) 小組夥伴 Allen 是用 object 做成表格來檢查，object 的 key 一定會是 string

1
2
3
4
5
6
7
8
9
10
11
12
const digits = {}
for (let i = 0; i < 10; i++) {
  digits[i] = i // 一開始有寫 digits[i + ""] 把 number 轉成 string
}
// digits = { "0": 0, "1": 1, "2": 2, ... , "9": 9 }

let result = 0
for (let i = index; i < s.length; i++) {
  if (digits[s[i]] !=== undefined) {// is digit
  result = result * 10 + digits[s[i]]
  } else break
}

(2) 聽完 Allen 講完隔天我自己寫這題的時候，是先把 digits 弄成 string 存到 array 中，然後用 if string[i] in array 來判斷 character 是否為數字

1
2
3
4
5
6
7
8
9
10
11
12
13
let digits = []
for (let j = 0; j < 10; j++) {
  digits.push(j + "") // 這邊把 number + "" 轉成 string 很妙
}
// digits = ["0", "1", "2", ... , "9"]

let number = 0
while (i < s.length) {
  if (s[i] in digits) {
    number = number * 10 + Number(s[i]) // 數字位移方式也是很多題目會使用到的
    i++
  } else break
}

(3) Alicia 分享的檢查 ASCII 碼是 String.prototype.charCodeAt()這個 method。我試著寫寫看：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let number = 0
while (i < s.length) {
  if (isDigits(s.charCodeAt(i))) {
    number = number * 10 + Number(s[i])
    i++
  } else break
} 

// 下方自建一個 function 判斷是否在 ASCII code 為數字區間
function isDigits (code) {
    if ((code >= 48) && (code <= 57)) { // numbers
      return true
    } else return false
}

memory 用量有下降，可能是因為不用另外存一個 array 或 object 表格去檢查了。

Leetcode 125. Valid Palindrome

同理也可以用來檢查是不是英文字、也可以轉大小寫

125. Valid Palindrome 在討論區中也有人用這個方法檢查、跳過非英文字母或數字（題目已經說 input string 限定 printable ASCII characters）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
var isPalindrome = function(input) {
    var start = 0
    var end = input.length - 1
    while (start < end) {
        var s = input.charCodeAt(start)
        var e = input.charCodeAt(end)
    
        if (!isLetter(s)) {
            start++
            continue
        }
        if (!isLetter(e)) {
            end--
            continue
        }
    
        if (toLowerCase(s) !== toLowerCase(e)) {
            return false 
        } 
        start++
        end--
  }
  return true
};

function isLetter (code) {
    if (((code >= 48) && (code <= 57))  // numbers
    || ((code >= 65) && (code <= 90))  // uppercase
    || ((code >= 97) && (code <= 122))) {  // lowercase
        return true
    }
    else {
        return false
    }
}

function toLowerCase (code) {
    if (code >= 65 && code <= 90) {
        return code + 32    
    }
    else {
        return code
    }
}

追求簡短的話還是 regex …如果可以直接寫出來的話XD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var isPalindrome = function(s) {
    const str = s.toLowerCase().replace(/[^a-z0-9]/gi, '')
    let left = 0
    let right = str.length - 1
    
    while (right > left) {
        if (str[left] !== str[right]) {
            return false
        } else {
            right--
            left++
    }
    }
        return true
};

再進化

1
2
3
4
var isPalindrome = function(s) {
    const alphaString = s.toLowerCase().replace(/[^a-z0-9]/gi, '')
    return alphaString.split('').reverse().join('') === alphaString
};

有時候寫題目不應該追求「最簡短」的解法，因為那通常都是別人想出來的，或是使用現成的 method 來套用，有時間的話可以了解其他方法，一題多解，在情境有變化的時候才會有更多工具可以使用！

Leetcode 709. To Lower Case

2023/01/03 更新

這題很單純，就是把字串裡的大寫字母換成小寫字母而已。

這邊要記錄的是，之前都用 string.charCodeAt(i) 去檢查 ASCII code 數字落在哪個範圍，但在 Javascript 中可以直接字串比大小！

1
2
3
4
5
6
7
8
9
10
var toLowerCase = function(s) {
    return Array.from(s).map(char => {
        if ((char >= "A") && (char <= "Z")) { // 字串比大小
            char = String.fromCharCode(char.charCodeAt(0) + 32)
            return char
        } else {
            return char
        }
    }).join('')
}

比對用之前的寫法，就少宣告一個函數，使用空間下降這樣。另外把 ASCII code 轉回字母是使用 String.fromCharCode(num)

  • String.prototype.charCodeAt() & String.fromCharCode(num1, num2, ...) 適用 UTF-16 code
  • String.prototype.codePointAt() & String.fromCodePoint(num1, num2, ...) for valid Unicode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 之前的寫法
var toLowerCase = function(s) {
    let i = 0
    let newString = ""
    while (i < s.length) {
        newString += String.fromCharCode(toLowerCaseCode(s.charCodeAt(i)))
        i++
    }
    return newString
};

function toLowerCaseCode (code) {
    if ((code >= 65) && (code <= 90)) { // uppercase
        return code + 32
    } else {
        return code
    }
}