跳转至

2828. 判别首字母缩略词

来源第 359 场周赛 Q1难度简单分数1151

题目描述

给你一个字符串数组 words 和一个字符串 s ，请你判断 s 是不是 words 的 首字母缩略词 。

如果可以按顺序串联 words 中每个字符串的第一个字符形成字符串 s ，则认为 s 是 words 的首字母缩略词。例如，"ab" 可以由 ["apple", "banana"] 形成，但是无法从 ["bear", "aardvark"] 形成。

如果 s 是 words 的首字母缩略词，返回 true ；否则，返回 false 。

 

示例 1：

输入：words = ["alice","bob","charlie"], s = "abc"
输出：true
解释：words 中 "alice"、"bob" 和 "charlie" 的第一个字符分别是 'a'、'b' 和 'c'。因此，s = "abc" 是首字母缩略词。

示例 2：

输入：words = ["an","apple"], s = "a"
输出：false
解释：words 中 "an" 和 "apple" 的第一个字符分别是 'a' 和 'a'。
串联这些字符形成的首字母缩略词是 "aa" 。
因此，s = "a" 不是首字母缩略词。

示例 3：

输入：words = ["never","gonna","give","up","on","you"], s = "ngguoy"
输出：true
解释：串联数组 words 中每个字符串的第一个字符，得到字符串 "ngguoy" 。
因此，s = "ngguoy" 是首字母缩略词。

 

提示：

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 10
  • 1 <= s.length <= 100
  • words[i] 和 s 由小写英文字母组成

解法

方法一：模拟

思考

首字母缩略词即每个单词首字符的拼接。一次遍历取出首字母并与 \(s\) 比较即可。

我们可以遍历数组 \(\textit{words}\) 中的每个字符串，将其首字母拼接起来，得到一个新的字符串 \(t\)，然后判断 \(t\) 是否等于 \(s\) 即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组 \(\textit{words}\) 的长度。

1
2
3
class Solution:
    def isAcronym(self, words: List[str], s: str) -> bool:
        return "".join(w[0] for w in words) == s

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean isAcronym(List<String> words, String s) {
        StringBuilder t = new StringBuilder();
        for (var w : words) {
            t.append(w.charAt(0));
        }
        return t.toString().equals(s);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    bool isAcronym(vector<string>& words, string s) {
        string t;
        for (auto& w : words) {
            t += w[0];
        }
        return t == s;
    }
};

1
2
3
4
5
6
7
func isAcronym(words []string, s string) bool {
    t := []byte{}
    for _, w := range words {
        t = append(t, w[0])
    }
    return string(t) == s
}

1
2
3
function isAcronym(words: string[], s: string): boolean {
    return words.map(w => w[0]).join('') === s;
}

1
2
3
4
5
6
7
8
9
impl Solution {
    pub fn is_acronym(words: Vec<String>, s: String) -> bool {
        words
            .iter()
            .map(|w| w.chars().next().unwrap_or_default())
            .collect::<String>()
            == s
    }
}

方法二：模拟（空间优化）

思考

方法一额外构造了长度为 \(n\) 的字符串。先比较 \(\textit{words}\) 与 \(s\) 的长度，再按下标逐个核对该词首字母，可将额外空间降为常数。

我们首先判断 \(\textit{words}\) 中的字符串个数是否等于 \(s\) 的长度，如果不等于，那么 \(s\) 一定不是 \(\textit{words}\) 的首字母缩略词，直接返回 \(\textit{false}\)。

然后我们遍历 \(s\) 的每个字符，判断其是否等于 \(\textit{words}\) 中对应字符串的首字母，如果不等于，那么 \(s\) 一定不是 \(\textit{words}\) 的首字母缩略词，直接返回 \(\textit{false}\)。

遍历结束后，如果没有返回 \(\textit{false}\)，那么 \(s\) 就是 \(\textit{words}\) 的首字母缩略词，返回 \(\textit{true}\)。

时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。其中 \(n\) 是数组 \(\textit{words}\) 的长度。

1
2
3
class Solution:
    def isAcronym(self, words: List[str], s: str) -> bool:
        return len(words) == len(s) and all(w[0] == c for w, c in zip(words, s))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public boolean isAcronym(List<String> words, String s) {
        if (words.size() != s.length()) {
            return false;
        }
        for (int i = 0; i < s.length(); ++i) {
            if (words.get(i).charAt(0) != s.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    bool isAcronym(vector<string>& words, string s) {
        if (words.size() != s.size()) {
            return false;
        }
        for (int i = 0; i < s.size(); ++i) {
            if (words[i][0] != s[i]) {
                return false;
            }
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func isAcronym(words []string, s string) bool {
    if len(words) != len(s) {
        return false
    }
    for i := range s {
        if words[i][0] != s[i] {
            return false
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function isAcronym(words: string[], s: string): boolean {
    if (words.length !== s.length) {
        return false;
    }
    for (let i = 0; i < words.length; i++) {
        if (words[i][0] !== s[i]) {
            return false;
        }
    }
    return true;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn is_acronym(words: Vec<String>, s: String) -> bool {
        if words.len() != s.len() {
            return false;
        }
        for (i, w) in words.iter().enumerate() {
            if w.chars().next().unwrap_or_default() != s.chars().nth(i).unwrap_or_default() {
                return false;
            }
        }
        true
    }
}

评论