简单聊聊字符串的翻转问题
字符串的翻转在日常开发使用程度比较少，但是面试过程中却是常有的。最近看php 源码中strrev，因此写一篇文记录对字符串翻转问题的一些学习。
对于字符串"Hello word" 翻转成"drow olleH"的问题，php有现成函数strrev可以解决。先看看php如何实现的
PHP_FUNCTION(strrev){
zend_string *str;
char *e, *p;
zend_string *n;
if (zend_parse_parameters(ZEND_NUM_ARGS(), "S", &str) == FAILURE) {
return;
}
n = zend_string_alloc(ZSTR_LEN(str), 0);
p = ZSTR_VAL(n);
e = ZSTR_VAL(str) + ZSTR_LEN(str);
while (--e >= ZSTR_VAL(str)) {
*p++ = *e;
}
*p = '\0';
RETVAL_NEW_STR(n);
}这其实对应一种解决方案。在一个循环中，把字符串从后往前复制到一个新的变量中去，然后返回。时间复制度是O(n),空间复制度O(n)。
另一种方案则是在原有字符串上做修改。分别设置两个标记变量。分别从字符串的前面，后面向中间靠拢，当两个标记相遇则结束。时间复制度O(n)，空间复杂度O(1)
$str = "Hello word";
$i = 0;
$j = strlen($str)-1;
while ($i <$j) {
$tmp = $str[$i];
$str[$i] = $str[$j];
$str[$j] = $tmp;
$i++;
$j--;
}网络上还有一种思路是使用异或运算交换两个字符，A^B^B = A,A^B^A = B。其实跟第二种思路类似，只是改变了赋值操作，不引入临时变量。这就跟"不引入其他变量，交换两个变量的值"一样（数值变量，或者等长度字符串变量）
$str = "Hello word";
$i = 0;
$j = strlen($str)-1;
while ($i <$j) {
$tmp = $str[$i];
$str[$i] = $str[$i]^$str[$j];
$str[$j] = $str[$i]^$str[$j];
$str[$i] = $str[$i]^$str[$j];
$i++;$j--;
}那么对于问题"student. a am I" 翻转成"I am a student."这类问题呢？这种问题，单次本身的顺序是正确的。单词之间的顺序是错误的。上面的问题处理单元是"字符",而这里的问题处理单元是"单词"
这类字符翻转有两种办法，一个先使用strrev翻转整个句子，然后再对里面的单词依次翻转。
$str = "student. a am I";
$str = strrev($str);
$str = implode(
' ',
array_map(function($word){
return strrev($word);
},
explode(' ', $str)
));第二类，则是直接调换单词顺序。
$str = "student. a am I";
$words = explode(' ', $str);
$i=0;$j = count($words)-1;
while ($i <$j) {
$tmp = $words[$i];
$words[$i] = $words[$j];
$words[$j] = $tmp;
$i++;
$j--;}$str = implode(' ', $words);
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-01-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读