题图来自 Unsplash
字符串翻转作为算法题已经是一个不能再基础的问题了, 无非就是逆序遍历, 双指针遍历, 递归, 代码也能分分钟写出来:
- 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 上绝对是能 AC 的, 但是实际情况中能 AC 吗? 答案肯定是不能的! 一个靠谱的字符串翻转算法题放到 LeetCode 上至少是 Medium 的难度.
首先我们知道字符串有编码规则, 比如我们常用的 UTF-8,Windows 早期采用的 UTF-16(函数名有 W 后缀的 API 采用这种编码) 等等... 对于英文字母等 ASCII 字符的情况, UTF-8 和 ASCII 编码都是一个字节, 所以上述的方法没有太大问题. 然而对于有中文的情况, 一个中文字符在 UTF-8 中会占 3 个字节, 如果单纯的按字节翻转就会出现乱码.
那怎么解决呢?
最简单的方法就是使用 mbstowcs 函数将 char * 类型的字符串转换为 wchar_t 类型的宽字符串, wchar_t 这个类型在 Linux,UNIX 系统上占 4 个字节, 在 Windows 上占 2 个字节. 4 个字节意味着字符将用 UTF-32 来编码, 不管是汉字还是 Emoji 都能存放下来. 但对于 2 个字节, 也就是 UTF-16, 汉字是能表示, 但是 Emoji 这类位于辅助平面码位的字符需要两个码元来表示, 本文的方法就暂不适用了.
首先我们来看一下改进版的字符串翻转:
- 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 这类转换函数首先需要设置字符串的系统编码, 不然函数无法确定你传入的 char * 是个什么东西, 本文中不管是源码还是系统环境的 std I/O 都采用 UTF-8 编码.
接下来我们调用一次 mbstowcs 不传入目标地址和字符长度, 这可以让函数直接计算所需的 wchar_t 个数并返回回来以便我们申请内存.
然后就是基于 wchar_t 的一个常规字符串翻转了, 最后别忘了转换回去, 释放内存即可.
Bonus: Cocoa 开发中的字符串翻转
作为 iOS 开发者, 当然还要考虑 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];
- }
复制代码
这种方法是效果最好的, 它会将 Composed Emoji(如 ) 也提取出来, 因为这类 Emoji 是由多个 Unicode 字符组合而成的, 所以即便是 4 个字节的 wchar_t 也容纳不下. 但这种方法的弊端就是开销太大, 稍后我们做一个比较.
方案 2:
通过 API 获取到 C String, 然后用文章开头所述的方法处理, 再重新用处理后的 C String 构造 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;
- }
复制代码
这种方法的好处就是高效, 经测试, 它与遍历的方法相比有 100 多倍的性能提升, 但是问题就是无法处理复杂的 Emoji.
两种方法, 在使用中需要好好衡量一下.
方案 3:
Swift.Swift 的 String 的基本单位是 Character, 它是 Unicode Scalar 的集合, 表示了一个可渲染的字符, 包括 Composed Emoji. 并且, String 是实现了
BidirectionalCollection
, 拥有 reversed 方法, 可以轻松实现字符串翻转. 另外要提醒大家一下, 正由于 Swift 的 String 是基于 Character 的, 对于取某个字符这样的操作, 能复用之前的 Index 就复用, 我见过很多人喜欢写
str.index(str.startIndex, offsetBy: i)
复制代码
这样是很费性能的, 因为 Index 的移动操作需要从起点遍历计算, 用这种方法遍历一遍字符串的复杂度近似是 O(n!).
大家有兴趣可以试试 Swift 的性能~
来源: https://juejin.im/post/5b533ea7e51d4519115d113d