惊！Rust 中这样操作字符串竟然是错的

文本在编程语言中是必不可少的。String 是 Rust 和 JavaScript 中定义用于处理世界各地书面语言中的文本。通过字符串索引的简单概念，我们将讨论 Rust 和 JavaScript 如何处理字符串，以及它们在如何处理字符串（如 grapheme，甚至表情符号）中的细微差别。

我们使用经典算法 is_palindrome 来介绍字符串索引的概念。

01 Rust 中的 is_palindrome

回文^[1]，以一种非常一般的方式解释它，是一个向前和向后阅读都相同的字符串。"Ana" 是回文，"A dog! A panic in a pagoda!" 是回文。

本文的目的，我们将使用更窄的定义来保持算法的简单性。此处的回文被定义为"不带空格的小写 ASCII 字符的连续序列"。

一种直观的方法是使用两个指针。一个从给定字符串的开头开始，向末尾移动，另一个从末尾开始。移动指针时，比较指向的字符。如果所有比较都相等，则给定的字符串是回文。类似这样：

// ❌ It won't compile
fn is_palindrome(str: String) -> bool {
  //        lp       rp
  //        |        |
  //        v →    ← v
  // str = "aabbccbbaa"
  let mut lp = 0;
  let mut rp = str.len() - 1;

  while lp < rp {
    if str[lp] != str[rp] {
    // ^^^^^^^ `String` cannot be indexed by `usize`
      return false;
    }
    lp += 1;
    rp -= 1;
  }

  true
}

如果你尝试编译程序，会注意到 Rust 编译器不允许我们按索引访问字符。这是一个非常有趣的约束，因为许多语言，如 JavaScript，Go 和 Python 都提供了该功能。

随着我们深入挖掘，标准库中有一些字符串方法（如`chars()`^[2]）来访问字符串中的字符。chars() 返回字符串切片 s 上的迭代器。因此，我们必须循环访问字符串切片以按索引访问字符。例如像这样：

let left = str.as_str().chars().nth(lp).unwrap();

访问字符串中字符这样简单的任务时间复杂度 是 O(n) 而不是  O(1)。

为什么？

02 Rust 的字符串采用 Unicode/UTF-8 编码

我们可以从官方的 Rust 书籍^[3]中找到 String 的内部表示^[4]。

字符串是 Vec的包装器。

对于 ASCII^[5] 中的字符串，每个字符由 1 个以 UTF-8^[6] 编码的字节表示。但是，对于其他书面语言中的字符串，例如 Rust 书中提到的 ["नमस्ते"](https://doc.rust-lang.org/book/ch08-02-strings.html#bytes-and-scalar-values-and-grapheme-clusters-oh-my) 每个字符都以 UTF-8 编码，具有多个 Unicode^[7] 值（代码单元，即码点）。

所以在 Rust 的书中，这样说：

索引字符串通常不是好的方式，因为不清楚字符串索引操作的返回类型应该是什么：字节、字符、字形群（a grapheme cluster）或字符串切片。

这是 Rust 编译器不允许直接访问字符串中的字符的原因之一。我真的建议你在 Rust 书中^[8]阅读更多关于它的信息。它非常容易阅读且有见地👏。

03 正确的 is_palindrome

我们可以迭代 bytes^[9]，并将字符串的前半部分与反向的后半部分进行比较。如果它们相等，这是一个回文：

// ✅
fn is_palindrome(str: String) -> bool {
    let half = str.len() / 2;
    let forward = str.bytes().take(half);
    let backward = str.bytes().rev().take(half);

    forward.eq(backward)
}

fn main() {
    assert_eq!(is_palindrome(String::from("")), true);
    assert_eq!(is_palindrome(String::from("aabbccbbaa")), true);
    assert_eq!(is_palindrome(String::from("aabbccbbab")), false);
}

时间和空间的复杂性：

• 时间复杂度：O(n)，其中 n 是字符串的长度
• 空间复杂度：O(n)，其中 n 是字符串的长度

空间复杂性 O(n) 是因为我们根据输入字符串的长度创建了两个字节迭代器。

04 TypeScript 中的isPalindrome

JavaScript 允许字符串索引。因此，我们实际上可以翻译在 rust 中编译不通过的双指针算法。

/*
 *  lp       rp
 *  |        |
 *  v →    ← v
 * "aabbccbbaa"
 */
function isPalindrome(str: string): boolean {
  let lp = 0
  let rp = str.length - 1

  while (lp < rp) {
    if (str[lp] !== str[rp]) {
      return false
    }
    lp += 1
    rp -= 1
  }
  return true
}

isPalindrome('') // true
isPalindrome('aabbccbbaa') // true
isPalindrome('aabbccbbab') // false

时间和空间的复杂性是：

• 时间复杂度：O(n)，其中 n 是字符串的长度
• 空间复杂度：O(1)，两个指针的常量空间

或者只是向前和向后比较字符串：

function isPalindrome(str: string): boolean {
  return str === str.split('').reverse().join('')
}

时间和空间的复杂性：

• 时间复杂度：O(n)，其中 n 是字符串的长度
• 空间复杂度：O(n)，其中 n 是字符串的长度

这在 JavaScript 中相当容易。这是否意味着 JavaScript 对字符串的处理方式与 Rust 不同？

05 JavaScript 字符串采用 UTF-16 编码

我们可以在 ECMAScript 标准^[10]中找到字符串原始（primitive）值的定义：

原始值是零个或多个 16 位无符号整数值的有限有序序列

字符串值是字符串类型的成员。序列中的每个整数值通常表示 UTF-16 文本的单个 16 位单位。

换句话说，每个 JavaScript 字符都用 Unicode 表示，占两个字节，并以 UTF-16 编码。

让我们看一些例子。我们可以使用一个或两个代码单元（码点）来创建一个字符：

const s1: string = '\u00E1' // á
const s2: string = '\u0061\u0301' // á

s1 和 s2 两者都是 á。如果我们检查两个字符串的长度：

console.log(s1.length) // 1
console.log(s2.length) // 2

即使它们都代表相同的字符，长度却是不同的。让我们通过字符串索引查看字符串内部，找出字符串中的元素：

console.log(s1[0]) // á
console.log(s1[1]) // undefined

console.log(s2[0]) // a
console.log(s2[1]) //  ́
console.log(s2[2]) //  undefined

我们可以看到 s2 由两个独立的元素组成，a 和 ́。

我们看到相同的字符可以以不同的方式表示，很明显 JavaScript 中的字符串索引也不可靠。

让我们检查一下相等性：

console.log(s1 === s2) // false 🧐

为了更有趣，还有另一种方法来表示 á：

const s3: string = 'a\u0301' // á

在 s3 中，我们将代码单元 \u0061 替换为其字符表示 a。运行检查下：

console.log(s3.length === 2) // true
console.log(s2 === s3) // true 🧐
console.log(s1 === s3) // false

到目前为止，我们看到的是由多个代码单元组合来表示同一个字符。相等性由代码单元组合定义。

它可能非常不方便，所以 JavaScript 引入了一个字符串方法  `normalize()`^[11] 来返回给定字符串的 Unicode 规范化形式。让我们尝试使用：

console.log(s1.normalize() === s2.normalize()) // true
console.log(s1.normalize() === s3.normalize()) // true

让我们来看看 á 规范化形式的内部

// `escape` is deprecated.
escape(s1.normalize()) // '%E1'
escape(s2.normalize()) // '%E1'
escape(s3.normalize()) // '%E1'

请注意，`escape()`^[12] 已从 ECMAScript 标准中删除。

由于规范化，现在处理字符串更加可预测。

JavaScript 实际上提供了一个官方的 Encoding API^[13]。我们可以使用 TextEncoder^[14] 和 TextDecoder^[15] 来处理字符串编码和解码。

const encoder = new TextEncoder()
const decoder = new TextDecoder()

const bytes = encoder.encode('\u0061\u0301')
decoder.decode(bytes) // 'á'

06 总结

字符串很复杂。Rust 提供了一个强大的系统来处理字符串，并提供了一个严格的编译器，以鼓励我们提前考虑字符串处理。另一方面，JavaScript 提供了方便的 API 来处理像 ASCII 这样的简单用例。在引擎层面，它们都实现了Unicode 标准和编码，以支持国际上的书面语言。

原文链接：https://dawchihliou.github.io/articles/indexing-strings-in-rust-and-typescript

参考资料