力扣面试经典——125题

💡 参考代码：

/**
 * 判断字符串是否为回文串
 * 
 * 解题思路：
 * 1. 使用双指针法，从字符串两端向中间移动
 * 2. 跳过所有非字母数字字符
 * 3. 将大写字母转换为小写进行比较
 * 4. 如果所有对应字符都相等，则为回文串
 * 
 * @param s 输入字符串
 * @return true 表示是回文串，false 表示不是回文串
 */
bool isPalindrome(char * s){
    // 检查输入是否为空指针
    if (s == NULL) {
        return true;
    }
    
    // 初始化双指针
    int left = 0;                    // 左指针指向字符串开头
    int right = strlen(s) - 1;       // 右指针指向字符串末尾
    
    // 当左指针小于右指针时继续循环
    while (left < right) {
        // 跳过左侧非字母数字字符
        while (left < right && !isalnum(s[left])) {
            left++;
        }
        
        // 跳过右侧非字母数字字符
        while (left < right && !isalnum(s[right])) {
            right--;
        }
        
        // 比较左右字符（转换为小写后比较）
        if (tolower(s[left]) != tolower(s[right])) {
            return false;  // 字符不相等，不是回文串
        }
        
        // 移动指针向中间靠拢
        left++;
        right--;
    }
    
    // 所有对应字符都相等，是回文串
    return true;
}

📖 总结：

点击展开题目总结

🤔 验证回文串

---

1️⃣ 题目核心信息

🎯 功能描述：判断一个字符串在去除所有非字母数字字符并转换为小写后，是否为回文串

📥 输入输出：

• 输入：char * s - 待判断的字符串
• 输出：bool - true表示是回文串，false表示不是回文串

---

2️⃣ 实现原理

💡 核心思路：使用双指针法从字符串两端向中间移动，跳过非字母数字字符并忽略大小写进行比较

📋 实现步骤：

1. 初始化左右两个指针分别指向字符串的开始和结束位置
2. 移动左指针跳过所有非字母数字字符
3. 移动右指针跳过所有非字母数字字符
4. 比较左右指针指向字符的小写形式，如果不相等则返回false
5. 继续向中间移动指针，重复步骤2-4直到指针相遇

---

3️⃣ 关键点解析

🎯 代码技巧

• 使用双指针法避免创建新字符串，节省空间
• 利用 isalnum() 函数判断字符是否为字母或数字
• 使用 tolower() 函数统一字符大小写进行比较
• 在循环中同时处理字符过滤和比较逻辑

4️⃣ 使用场景

✅ 适用情况：

• 需要验证文本是否为回文格式
• 文本预处理后判断对称性
• 验证标识符或代码中的回文模式

⚠️ 前提条件：

• 输入字符串为ASCII字符
• 需要忽略大小写和非字母数字字符

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n)，其中n为字符串长度，每个字符最多被访问一次

• 💾 空间复杂度：O(1)，只使用了常数级别的额外空间

6️⃣ 注意事项

🚩 边界情况：

• 空字符串或NULL指针
• 只包含非字母数字字符的字符串
• 单个字符的字符串

💥 易错点：

• 忘记跳过非字母数字字符
• 忽略大小写转换导致判断错误
• 指针边界条件处理不当导致数组越界

7️⃣ 补充说明

函数的工作原理：

1.输入检查：首先检查输入字符串是否为 NULL，如果是则返回 true

2.双指针初始化：使用两个指针，left 指向字符串开始，right 指向字符串结束

3.双指针向中间移动：跳过非字母数字字符，只比较有效字符

4.字符比较：将字符转换为小写后进行比较

5.返回结果：如果所有对应字符都匹配，则返回 true，否则返回 false

例：简单回文 "A man, a plan, a canal: Panama"

原始字符串: "A man, a plan, a canal: Panama"
有效字符:   A m a n a p l a n a c a n a l P a n a m a
转换为小写: a m a n a p l a n a c a n a l p a n a m a

执行过程：

1.left=0 指向 'A'，right=32 指向 'a'

2.比较 tolower('A')和 tolower('a')，都是'a'，相等

3.继续向中间移动指针，跳过逗号和空格等非字母数字字符

4.依次比较每一对字符：(m,m), (a,a), (n,n)...

5.所有对应字符都相等，返回 true

加载评论中...