专栏首页写PHP的老王简单聊聊字符串的翻转问题

简单聊聊字符串的翻转问题

字符串的翻转在日常开发使用程度比较少,但是面试过程中却是常有的。最近看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);
}

本文分享自微信公众号 - 写PHP的老王(laowang_php),作者:写PHP的老王

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 用php实现字符串大小写转函数的功能

    在php中,最终使用的是c语言的toupper,tolower函数将字符进行大小写转换。因此需要定义一个字符大小写转换的函数。

    写PHP的老王
  • Laravel 中Facade门面是怎么实现?有没有其他实现方式?

    在laravel中的路由文件routes/web.php有这么一段代码,用于配置路由。这里Route就是用Facade实现类方法get的静态调用。

    写PHP的老王
  • 细读Yii2的Response

    一个完整的网络请求,最后都需要一个符合协议的返回。Yii2在处理web请求之后,统一通过web/Response处理返回。错误也会经过错误处理返回一个Respo...

    写PHP的老王
  • 对input进行输入金额控制(保留小数点后一位)

    在我们的项目中使用的VantUI,因为封装的输入框(文字,数字)都是用的van-field。但是项目需求是对输入金额时做一定对限制: (1).第一位只能输入数...

    honey缘木鱼
  • 使用validator.js对字符串数据进行验证

    validator.js是一个对字符串进行数据验证和过滤的工具库,同时支持Node端和浏览器端,github地址是https://github.com/chri...

    用户1515472
  • python内置模块之string

    str.capitalize() 把字符串的第一个字符大写 str.center(width) 返回一个原字符串居中,并使用空格填充到width长度的...

    菲宇
  • PAT(乙级)1014

    这道题目,略显(真TM坑爹,抱歉,我又说脏话了,但是实在不能忍啊!!!)坑爹。题目的意思看起来说的很清楚,实则完全没有说清楚,题目是“横看成岭侧成峰”啊!,但是...

    zy010101
  • C/C++踩坑记录(二)一段有趣的常量字符串 原

    测试平台: Ubuntu 16.04 Windows Mingw GCC gcc version 5.3.0 (i686-posix-dwarf-rev0,...

    Pulsar-V
  • 金额转大写

    在处理财务账款时,需要将转账金额写成大写的。也就是说,如果要转账123456.00元,则需要写成“壹拾贰万叁仟肆佰伍拾陆元整”。 所以常常需要通过程序控制自动进...

    崔笑颜

扫码关注云+社区

领取腾讯云代金券