详细谈谈iOS字符串翻转
前言
字符串翻转作为算法题已经是一个不能再基础的问题了,无非就是逆序遍历、双指针遍历、递归,代码也能分分钟写出来:
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 的性能~
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对的支持。
推荐阅读