写PHP的老王-简单聊聊字符串的翻转问题

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

29 Jan 2019 Category: 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);

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

评论