当前位置: 面试刷题>> 检查缩写字 (经典算法题500道)


题目描述

给定一个完整句子和一个缩写词,请编写一个函数来检查这个缩写词是否可以从完整句子中正确生成。缩写词的生成规则如下:

  1. 缩写词中的每个字母必须按顺序出现在完整句子中。
  2. 缩写词中的每个字母可能对应完整句子中的一个或多个连续字母(例如,'word' 可以缩写为 'wrd' 但不能缩写为 'wod')。
  3. 缩写词中的字母不区分大小写,但在判断时需要考虑句子中的字母大小写。
  4. 缩写词中的非字母字符(如空格、标点符号等)应忽略不计。

示例

  • 输入:句子 = "Hello World",缩写词 = "HW"

  • 输出:true

  • 输入:句子 = "i love coding", 缩写词 = "ic"

  • 输出:true

  • 输入:句子 = "i love coding", 缩写词 = "il"

  • 输出:false(因为 'l' 在句子中对应的 'l' 后面紧跟着 'o',而不是 'v')

PHP 代码示例

function isValidAbbreviation($sentence, $abbreviation) {
    $sentence = strtolower($sentence); // 转换为小写以忽略大小写差异
    $abbrLen = strlen($abbreviation);
    $sentenceLen = strlen($sentence);
    $i = 0; // 句子中的索引
    $j = 0; // 缩写词中的索引

    while ($i < $sentenceLen && $j < $abbrLen) {
        if (ctype_alpha($abbreviation[$j])) { // 检查当前缩写字符是否为字母
            while ($i < $sentenceLen && strtolower($sentence[$i]) != $abbreviation[$j]) {
                $i++; // 跳过非匹配字符
            }
            if ($i < $sentenceLen) {
                $i++; // 匹配成功,移动到句子的下一个字符
            }
        }
        $j++; // 移动到缩写词的下一个字符
    }

    return $j == $abbrLen; // 检查是否完全遍历了缩写词
}

// 测试示例
echo isValidAbbreviation("Hello World", "HW") ? "true" : "false"; // 输出 true
echo "\n";
echo isValidAbbreviation("i love coding", "ic") ? "true" : "false"; // 输出 true
echo "\n";
echo isValidAbbreviation("i love coding", "il") ? "true" : "false"; // 输出 false

Python 代码示例

def isValidAbbreviation(sentence, abbreviation):
    sentence = sentence.lower()
    i, j = 0, 0
    
    while i < len(sentence) and j < len(abbreviation):
        if abbreviation[j].isalpha():
            while i < len(sentence) and sentence[i] != abbreviation[j].lower():
                i += 1
            if i < len(sentence):
                i += 1
        j += 1
        
    return j == len(abbreviation)

# 测试示例
print(isValidAbbreviation("Hello World", "HW")) # 输出 True
print(isValidAbbreviation("i love coding", "ic")) # 输出 True
print(isValidAbbreviation("i love coding", "il")) # 输出 False

JavaScript 代码示例

function isValidAbbreviation(sentence, abbreviation) {
    sentence = sentence.toLowerCase();
    let i = 0, j = 0;

    while (i < sentence.length && j < abbreviation.length) {
        if (abbreviation[j].match(/[a-z]/i)) { // 检查缩写字符是否为字母
            while (i < sentence.length && sentence[i] !== abbreviation[j].toLowerCase()) {
                i++;
            }
            if (i < sentence.length) {
                i++;
            }
        }
        j++;
    }

    return j === abbreviation.length;
}

// 测试示例
console.log(isValidAbbreviation("Hello World", "HW")); // 输出 true
console.log(isValidAbbreviation("i love coding", "ic")); // 输出 true
console.log(isValidAbbreviation("i love coding", "il")); // 输出 false

码小课:在码小课的网站上,你可以找到更多关于算法和数据结构的精彩内容,涵盖从基础到进阶的各种编程技能,帮助你不断提升自己的编程能力。

推荐面试题