current position:Home>leetcode 2062. Count Vowel Substrings of a String(python)

leetcode 2062. Count Vowel Substrings of a String(python)

2022-01-31 06:03:34 Wang Daya

「 This is my participation 11 The fourth of the yuegengwen challenge 9 God , Check out the activity details :2021 One last more challenge

describe

A substring is a contiguous (non-empty) sequence of characters within a string.

A vowel substring is a substring that only consists of vowels ('a', 'e', 'i', 'o', and 'u') and has all five vowels present in it.

Given a string word, return the number of vowel substrings in word.

Example 1:

Input: word = "aeiouu"
Output: 2
Explanation: The vowel substrings of word are as follows (underlined):
- "aeiouu"
- "aeiouu"
 Copy code 

Example 2:

Input: word = "unicornarihan"
Output: 0
Explanation: Not all 5 vowels are present, so there are no vowel substrings.
 Copy code 

Example 3:

Input: word = "cuaieuouac"
Output: 7
Explanation: The vowel substrings of word are as follows (underlined):
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
 Copy code 

Example 4:

Input: word = "bbaeixoubb"
Output: 0
Explanation: The only substrings that contain all five vowels also contain consonants, so there are no vowel substrings.
 Copy code 

Note:

1 <= word.length <= 100
word consists of lowercase English letters only.
 Copy code 

analysis

According to the meaning , Given a string word word , Let's go back to word How many of them vowel substrings , The title also gives vowel substrings The definition of , That is a non empty substring and just contains a、e、i、o、u Five lowercase letters , But there is no limit to the number .

Use violence first , It's very simple :

  • Initialization result reuslt by 0
  • Traverse range(5, len(word) + 1) Every element in L , Indicates the length of the current substring
  • Then traverse ange(len(word) - L + 1) Of each element in i , Indicates from index i Start looking for substrings
  • With built-in functions collections.Counter Calculation word[i:i + L] The characters in , If meet vowel substrings Conditions , The result will be result Add one
  • Return after traversal result that will do

From the results of operation , Although it is more than 100% , But it doesn't mean that violent solutions are effective , Maybe it's a new question , The number of people submitting answers is too small . People should have a clear understanding of their abilities .

answer

class Solution(object):
    def countVowelSubstrings(self, word):
        """
        :type word: str
        :rtype: int
        """
        result = 0
        for L in range(5, len(word) + 1):
            for i in range(len(word) - L + 1):
                c = collections.Counter(word[i:i + L])
                keys = c.keys()
                if 'a' in keys and 'e' in keys and 'i' in keys and 'o' in keys and 'u' in keys and len(keys) == 5:
                    result += 1
        return result

        	      
		
 Copy code 

Running results

Runtime: 2676 ms, faster than 100.00% of Python online submissions for Count Vowel Substrings of a String.
Memory Usage: 13.4 MB, less than 100.00% of Python online submissions for Count Vowel Substrings of a String.
 Copy code 

analysis

In fact, you can use set functions set Simplify the above code .

answer

class Solution(object):
    def countVowelSubstrings(self, word):
        """
        :type word: str
        :rtype: int
        """
        return sum(set(word[i:i+L]) == set('aeiou') for L in range(5, len(word)+1) for i in range(len(word)-L+1))
        
 Copy code 

Running results

Runtime: 316 ms, faster than 100.00% of Python online submissions for Count Vowel Substrings of a String.
Memory Usage: 13.5 MB, less than 100.00% of Python online submissions for Count Vowel Substrings of a String.
 Copy code 

analysis

You can use a method similar to sliding window to solve problems , The idea is simple :

  • Initialize the result first result by 0 , Original sound set vowels by {'a','e','i','o','u'}
  • because vowel substring The shortest is 5 , So traverse range(len(word)-4) Every element in i , Indicates the start index of the substring
  • If word[i] stay vowel in , Create a new set s take word[i] Join in
  • Then traverse range(i+1, len(word)) Every element in j , Represents traversal i Characters after index , If word[j] be not in vowels explain word[i:j] Cannot constitute vowel substring , direct break Carry out the following cycle , Otherwise it would be word[j] Join in s in , If s The length of is 5 Description can constitute vowel substring 了 ,result Add one
  • At the end of the above two-layer cycle, return to result

As you can see from the results , The operation time is greatly improved .

answer

class Solution(object):
    def countVowelSubstrings(self, word):
        """
        :type word: str
        :rtype: int
        """
        result = 0
        vowels = {'a','e','i','o','u'}
        for i in range(len(word)-4):
            if word[i] in vowels:
                s = set(word[i])
                for j in range(i+1, len(word)):
                    if word[j] not in vowels:
                        break
                    s.add(word[j])
                    if len(s) == 5:
                        result += 1
        return result
        
 Copy code 

Running results

Runtime: 52 ms, faster than 100.00% of Python online submissions for Count Vowel Substrings of a String.
Memory Usage: 13.5 MB, less than 100.00% of Python online submissions for Count Vowel Substrings of a String.
 Copy code 

Original link :leetcode.com/problems/co…

Your support is my greatest motivation

copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201310603322851.html

Random recommended