跳到主要内容

单词规律

· 阅读需 5 分钟
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——290题​

💡 参考代码：​

/**
 * 判断字符串s是否遵循pattern的规律
 * @param pattern: 规律字符串，由小写字母组成
 * @param s: 待检测字符串，由空格分隔的单词组成
 * @return: 如果s遵循pattern规律返回true，否则返回false
 */
bool wordPattern(char * pattern, char * s){
    // 用于存储pattern中每个字符对应的单词
    char* charToWord[26] = {NULL};  // 26个字母的映射表
    
    // 用于存储已映射的单词，避免多个字符映射到同一个单词
    char* usedWords[3000];  // 最多3000个单词
    int wordCount = 0;
    
    // 复制字符串s，因为strtok会修改原字符串
    char* sCopy = malloc(strlen(s) + 1);
    strcpy(sCopy, s);
    
    // 使用空格分割字符串s
    char* token = strtok(sCopy, " ");
    
    // 遍历pattern中的每个字符
    for(int i = 0; pattern[i] != '\0'; i++){
        // 如果s中的单词已经用完，但pattern还有字符，返回false
        if(token == NULL){
            free(sCopy);
            return false;
        }
        
        char currentChar = pattern[i];  // 当前pattern字符
        char* currentWord = token;      // 当前单词
        
        // 计算字符在数组中的索引(相对于'a')
        int charIndex = currentChar - 'a';
        
        // 检查当前字符是否已经有映射
        if(charToWord[charIndex] == NULL){
            // 检查当前单词是否已经被其他字符映射
            for(int j = 0; j < wordCount; j++){
                if(strcmp(usedWords[j], currentWord) == 0){
                    free(sCopy);
                    return false;
                }
            }
            
            // 建立新的映射关系
            charToWord[charIndex] = malloc(strlen(currentWord) + 1);
            strcpy(charToWord[charIndex], currentWord);
            usedWords[wordCount] = malloc(strlen(currentWord) + 1);
            strcpy(usedWords[wordCount], currentWord);
            wordCount++;
        } else {
            // 检查现有映射是否与当前单词匹配
            if(strcmp(charToWord[charIndex], currentWord) != 0){
                free(sCopy);
                return false;
            }
        }
        
        // 获取下一个单词
        token = strtok(NULL, " ");
    }
    
    // 检查是否还有多余的单词
    if(token != NULL){
        free(sCopy);
        return false;
    }
    
    // 释放分配的内存
    for(int i = 0; i < 26; i++){
        if(charToWord[i] != NULL){
            free(charToWord[i]);
        }
    }
    for(int i = 0; i < wordCount; i++){
        free(usedWords[i]);
    }
    free(sCopy);
    
    return true;
}

📖 总结：​

点击展开题目总结

🤔 单词规律

1️⃣ 题目核心信息​

🎯 功能描述：判断字符串s中的单词是否按照pattern字符串的规律排列，需要建立字符与单词之间的双向唯一映射关系

📥 输入输出：

  • 输入：
    • pattern：规律字符串，只包含小写英文字母
    • s：待检测字符串，包含空格分隔的小写英文字母单词
  • 输出：布尔值，表示s是否遵循pattern的规律

2️⃣ 实现原理​

💡 核心思路：使用哈希表建立字符与单词的双向映射关系，并验证这种映射的一致性

📋 实现步骤：

  1. 使用数组作为哈希表存储每个字符对应的单词
  2. 使用另一个数组记录已映射的单词，确保双向唯一性
  3. 按空格分割字符串s，同时遍历pattern字符和单词
  4. 对每个字符-单词对验证映射关系的一致性

3️⃣ 关键点解析​

🎯 代码技巧​

  • 使用字符减去'a'的ASCII值作为数组索引，实现简单的哈希映射
  • 双向映射检查：既要检查字符是否已有映射，也要检查单词是否已被其他字符映射
  • 使用strtok函数方便地按分隔符分割字符串

4️⃣ 使用场景​

✅ 适用情况：​

  • 需要验证两个序列之间是否存在一一对应的映射关系
  • 模式匹配问题，如模板验证
  • 双射关系验证场景

⚠️ 前提条件：​

  • pattern只包含小写英文字母
  • s中的单词由单个空格分隔且不含前导或尾随空格

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(n×m)，其中n是pattern长度，m是平均单词长度
  • 💾 空间复杂度：O(n×m)，用于存储映射关系和分割后的单词

🚩 边界情况：​

  • pattern长度与单词数量不相等
  • 空字符串或单字符pattern
  • 单个单词或无单词的字符串s

💥 易错点：​

  • 忘记检查双向映射关系，只检查了字符到单词的映射
  • 没有正确处理内存分配和释放导致内存泄漏
  • 忽略了pattern遍历完后还需要检查是否还有剩余单词的情况

7️⃣ 补充说明​

以 pattern = "abba", s = "dog cat cat dog" 为例，逐步执行代码：

  1. 初始化数据结构：

    • charToWord[26] 全部为 NULL
    • usedWords[] 为空
    • 使用 strtok 分割字符串 s 得到单词序列：["dog", "cat", "cat", "dog"]

  2. 第一次循环 (i=0):

    • currentChar = 'a', currentWord = "dog"
    • charIndex = 'a' - 'a' = 0
    • charToWord[0] 为 NULL，建立新映射：
      • charToWord[0] = "dog"
      • usedWords[0] = "dog"
      • wordCount = 1

  3. 第二次循环 (i=1):

    • currentChar = 'b', currentWord = "cat"
    • charIndex = 'b' - 'a' = 1
    • charToWord[1] 为 NULL，建立新映射：
      • charToWord[1] = "cat"
      • usedWords[1] = "cat"
      • wordCount = 2

  4. 第三次循环 (i=2):

    • currentChar = 'b', currentWord = "cat"
    • charIndex = 'b' - 'a' = 1
    • charToWord[1] 已存在且等于 "cat"，映射一致，继续执行

  5. 第四次循环 (i=3):

    • currentChar = 'a', currentWord = "dog"
    • charIndex = 'a' - 'a' = 0
    • charToWord[0] 已存在且等于 "dog"，映射一致，继续执行

  6. 检查是否还有剩余单词：

    • token = strtok(NULL, " ") 返回 NULL，没有剩余单词

  7. 返回 true，表示匹配成功

这个例子展示了正确的双向映射关系：'a' ↔ "dog"，'b' ↔ "cat"，且按照 "abba" 的模式排列。

加载评论中...