前言

字符串翻轉(zhuǎn)作為算法題已經(jīng)是一個(gè)不能再基礎(chǔ)的問題了，無非就是逆序遍歷、雙指針遍歷、遞歸，代碼也能分分鐘寫出來：

void strrev(char *str) {
 size_t start = 0;
 size_t end = start + strlen(str) - 1;

 while (start < end) {
  char ch = str[start];
  str[start++] = str[end];
  str[end--] = ch;
 }
}

OK，上面的代碼放到 LeetCode 上絕對(duì)是能 AC 的，但是實(shí)際情況中能 AC 嗎？答案肯定是不能的！一個(gè)靠譜的字符串翻轉(zhuǎn)算法題放到 LeetCode 上至少是 Medium 的難度。

首先我們知道字符串有編碼規(guī)則，比如我們常用的 UTF-8，Windows 早期采用的 UTF-16（函數(shù)名有 W 后綴的 API 采用這種編碼）等等...對(duì)于英文字母等 ASCII 字符的情況，UTF-8 和 ASCII 編碼都是一個(gè)字節(jié)，所以上述的方法沒有太大問題。然而對(duì)于有中文的情況，一個(gè)中文字符在 UTF-8 中會(huì)占 3 個(gè)字節(jié)，如果單純的按字節(jié)翻轉(zhuǎn)就會(huì)出現(xiàn)亂碼。

那怎么解決呢？

最簡(jiǎn)單的方法就是使用 mbstowcs 函數(shù)將 char * 類型的字符串轉(zhuǎn)換為 wchar_t 類型的寬字符串，wchar_t 這個(gè)類型在 Linux、UNIX 系統(tǒng)上占 4 個(gè)字節(jié)，在 Windows 上占 2 個(gè)字節(jié)。4 個(gè)字節(jié)意味著字符將用 UTF-32 來編碼，不管是漢字還是 Emoji 都能存放下來。但對(duì)于 2 個(gè)字節(jié)，也就是 UTF-16，漢字是能表示，但是 Emoji 這類位于輔助平面碼位的字符需要兩個(gè)碼元來表示，本文的方法就暫不適用了。

首先我們來看一下改進(jìn)版的字符串翻轉(zhuǎn)：

static void strrev2(char *str) {
 setlocale(LC_CTYPE, "UTF-8");
 size_t len = mbstowcs(NULL, str, 0);
 wchar_t *wcs = (wchar_t *) calloc(len + 1, sizeof(wchar_t));
 mbstowcs(wcs, str, len + 1);

 size_t start = 0;
 size_t end = start + len - 1;

 while (start < end) {
  wchar_t wc = wcs[start];
  wcs[start++] = wcs[end];
  wcs[end--] = wc;
 }

 wcstombs(str, wcs, wcstombs(NULL, wcs, 0));
 free(wcs);
}

使用 mbstowcs 這類轉(zhuǎn)換函數(shù)首先需要設(shè)置字符串的系統(tǒng)編碼，不然函數(shù)無法確定你傳入的 char * 是個(gè)什么東西，本文中不管是源碼還是系統(tǒng)環(huán)境的 std I/O 都采用 UTF-8 編碼。

接下來我們調(diào)用一次 mbstowcs 不傳入目標(biāo)地址和字符長(zhǎng)度，這可以讓函數(shù)直接計(jì)算所需的 wchar_t 個(gè)數(shù)并返回回來以便我們申請(qǐng)內(nèi)存。

然后就是基于 wchar_t 的一個(gè)常規(guī)字符串翻轉(zhuǎn)了，最后別忘了轉(zhuǎn)換回去，釋放內(nèi)存即可。

Bonus: Cocoa 開發(fā)中的字符串翻轉(zhuǎn)

作為 iOS 開發(fā)者，當(dāng)然還要考慮 OC 中的解決方法了。

方案 1：

通過 API 遍歷子串，然后前向插入到新的 NSMutableString 中。

- (NSString *)my_stringByReversing {
 NSMutableString *reversed = [NSMutableString stringWithCapacity:self.length];
 NSRange range = NSMakeRange(0, self.length);
 [self enumerateSubstringsInRange:range
        options:NSStringEnumerationByComposedCharacterSequences
       usingBlock:^(NSString * _Nullable substring, NSRange substringRange,
          NSRange enclosingRange, BOOL * _Nonnull stop) {
        [reversed insertString:substring atIndex:0];
       }];
 return [reversed copy];
}

這種方法是效果最好的，它會(huì)將 Composed Emoji（如 👨‍👩‍👧‍👧）也提取出來，因?yàn)檫@類 Emoji 是由多個(gè) Unicode 字符組合而成的，所以即便是 4 個(gè)字節(jié)的 wchar_t 也容納不下。但這種方法的弊端就是開銷太大，稍后我們做一個(gè)比較。

方案 2：

通過 API 獲取到 C String，然后用文章開頭所述的方法處理，再重新用處理后的 C String 構(gòu)造 NSString。

- (NSString *)my_stringByReversing2 {
 NSUInteger length = [self lengthOfBytesUsingEncoding:NSUTF8StringEncoding];
 char *buf = calloc(length + 1, 1);
 [self getCString:buf maxLength:length + 1 encoding:NSUTF8StringEncoding];
 strrev2(buf);
 NSString *reversed = [NSString stringWithCString:buf encoding:NSUTF8StringEncoding];
 free(buf);
 return reversed;
}

這種方法的好處就是高效，經(jīng)測(cè)試，它與遍歷的方法相比有 100 多倍的性能提升，但是問題就是無法處理復(fù)雜的 Emoji。

兩種方法，在使用中需要好好衡量一下。

方案 3：

Swift。Swift 的 String 的基本單位是 Character，它是 Unicode Scalar 的集合，表示了一個(gè)可渲染的字符，包括 Composed Emoji。并且，String 是實(shí)現(xiàn)了 BidirectionalCollection，擁有 reversed 方法，可以輕松實(shí)現(xiàn)字符串翻轉(zhuǎn)。另外要提醒大家一下，正由于 Swift 的 String 是基于 Character 的，對(duì)于取某個(gè)字符這樣的操作，能復(fù)用之前的 Index 就復(fù)用，我見過很多人喜歡寫

str.index(str.startIndex, offsetBy: i)

這樣是很費(fèi)性能的，因?yàn)?Index 的移動(dòng)操作需要從起點(diǎn)遍歷計(jì)算，用這種方法遍歷一遍字符串的復(fù)雜度近似是 O(n!)。

大家有興趣可以試試 Swift 的性能~

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，如果有疑問大家可以留言交流，謝謝大家對(duì)腳本之家的支持。

最新評(píng)論