字串的前半和後半是否相似 If String Halves Are Alike_Leetcode #1704

DAVIDCOHEN null on Unsplash

題目敘述

題目會給我們一個輸入字串s，題目還保證字串s的長度一定是偶數。

要求我們判定字串s的前半部和後半部是否相似?

註: 母音英文字母為a, e, i, o, u, A, E, I, O, U

題目的原文敘述

測試範例

Example 1:

Input: s = "book"
Output: true
Explanation: a = "bo" and b = "ok". a has 1 vowel and b has 1 vowel. Therefore, they are alike.

Example 2:

Input: s = "textbook"
Output: false
Explanation: a = "text" and b = "book". a has 1 vowel whereas b has 2. Therefore, they are not alike.
Notice that the vowel o is counted twice.

約束條件

• 2 <= s.length <= 1000

字串s的長度介於2~1000之間。

• s.length is even.

字串s的長度一定是偶數。

• s consists of uppercase and lowercase letters.

字串s只會包含大寫和小寫的英文字母。

演算法

因為題目已經保證字串s長度一定是偶數，因此，直接從中心點分割字串，分別計算前半段的母音數量，和後半段的母音數量，若兩者擁有的母音數量相同，則兩個字串是相似字串。

python裡面有一個實用的切片語法，

s[:索引編號]可以切出從s[0]~s[索引編號-1]的字串。

s[索引編號:]可以切出從s[索引編號]~s[len(s)-1]的字串。

第一次接觸切片語法slice的同學，可以參考這裡的官方文件說明

程式碼

class Solution:
    def halvesAreAlike(self, s: str) -> bool:
        
        # --------------------------------------------------------
        def countVowels(s):
            
            # compute and return the number of vowel letters in s
            vowel = set("aeiouAEIOU")            
            
            return sum( 1 for char in s if char in vowel )
        
        # --------------------------------------------------------
        
        size = len(s)
        
        # It is guaranteed that s is of even length
        midpoint = size // 2
        
        # get substring of a as well as b
        a, b = s[:midpoint], s[midpoint:]
        
        # check with definition of "alike", given by description
        return countVowels(a) == countVowels(b)

複雜度分析

時間複雜度:

切割時間耗費O(n)，計算字串裡面的母音數量已耗費O(n)，總共所需時間為O(n)

空間複雜度:

會需要額外的兩個臨時空間去儲存字串的前半段a和後半段b，所需空間為O(n)

Reference:

[1] Determine if String Halves Are Alike - LeetCode