移动指针 VS.只是迭代字符串

Question

我是准备面试问题的初学者。我最近有一个关于迭代字符串的问题。

在处理"有效回文"和类似问题时，我们通常有两种方法可以解决问题。

我们要么不断更新指针，直到找到目标字符：

s = s.toLowerCase();
int lo = 0;
int hi = s.length() - 1;
while(hi > lo){
    while(lo < hi && !Character.isLetterOrDigit(s.charAt(lo))) lo ++;
    while(hi > lo && !Character.isLetterOrDigit(s.charAt(hi))) hi --;
    if(s.charAt(lo) != s.charAt(hi)) return false;
    lo ++;
    hi --;
}
return true;

或者只是迭代字符串（来自leetcode讨论）：

int head = 0, tail = s.length() - 1;
char cHead, cTail;
while(head <= tail) {
    cHead = s.charAt(head);
    cTail = s.charAt(tail);
    if (!Character.isLetterOrDigit(cHead)) {
        head++;
    } else if(!Character.isLetterOrDigit(cTail)) {
        tail--;
    } else {
        if (Character.toLowerCase(cHead) != Character.toLowerCase(cTail)) {
            return false;
        }
        head++;
        tail--;
    }
}
return true;

我不确定哪种方法在大O分析方面更好，在面试中使用哪种方法？

提前感谢！

Answer 1

第二个更好。

• 第一种还治疗lo == hi和
• 重复外循环的条件。
• 此外，对同一索引重复charAt。（虽然在第二个cTail中可能没有被得到。

二是不太复杂，比较懒惰，处理小案子，小步骤，容易验证。

第二个可以用更好的风格写成：

//char cHead, cTail;
while(head <= tail) {
    char cHead = s.charAt(head);
    char cTail = s.charAt(tail);

由于循环中的声明没有开销，因此只为变量保留了一个堆栈变量。