Поиск подмассивов гласных по заданной строке

Question

Вам дана строка S, и вы должны найти все удивительные подстроки S.

Удивительная подстрока - это та, которая начинается с гласной (a, e, i, o, u, A,E, I, O, U).

Ввод

Единственный аргумент - строка S.

Выход

Возвращает одно целое число X mod 10003, здесь X - количество Удивительных подстрок в данной строке.

Ограничения

• 1 <= длина(S) <= 1e6 </li>
• S может иметь специальные символы

Пример

Input
    ABEC

Output
    6

Explanation
    Amazing substrings of given string are :
    1. A
    2. AB
    3. ABE
    4. ABEC
    5. E
    6. EC
    here number of substrings are 6 and 6 % 10003 = 6.

Я реализовал следующий алгоритм длявыше Проблема.

    class Solution:
        # @param A : string
        # @return an integer
        def solve(self, A):
            x = ['a', 'e','i','o', 'u', 'A', 'E', 'I', 'O', 'U']
            y = []
            z = len(A)
            for i in A:
                if i in x:
                    n = A.index(i)
                    m = z
                    while m > n:
                        y.append(A[n:m])
                        m -= 1
            if y:
                return len(y)%10003
            else:
            return 0

Выше Решение отлично работает для строк нормальной длины, но не для большей длины.

Например,

A = "pGpEusuCSWEaPOJmamlFAnIBgAJGtcJaMPFTLfUfkQKXeymydQsdWCTyEFjFgbSmknAmKYFHopWceEyCSumTyAFwhrLqQXbWnXSn"

Выше Алговыводит 1630 подмассивов, но ожидаемый ответ 1244 .

Пожалуйста, помогите мне улучшить вышеприведенный алгоритм.Спасибо за помощь

Answer 1

Сосредоточьтесь на требуемом выводе: вам не нужно находить все эти подстроки.Все, что вам нужно, это количество подстрок.

Посмотрите еще раз на ваш короткий пример, ABEC.Есть два гласных, A и E.

• A в местоположении 0. Всего имеется 4 подстроки, заканчивающиеся там и в каждом следующем местоположении.
• E находится в местоположении 2. Всего имеется 2 подстроки, заканчивающиеся там и в каждом следующем местоположении.

2 + 4 => 6

Все, что вам нужно сделать, это найтиположение каждой гласной, вычтите из длины строки и накапливайте эти различия:

A = "pGpEusuCSWEaPOJmamlFAnIBgAJGtcJaMPFTLfUfkQKXeymydQsdWCTyEFjFgbSmknAmKYFHopWceEyCSumTyAFwhrLqQXbWnXSn"

lenA = len(A)
vowel = "aeiouAEIOU"
count = 0

for idx, char in enumerate(A):
    if char in vowel:
       count += lenA - idx

print(count%10003)

Вывод:

1244

В одной команде:

print( sum(len(A) - idx if char.lower() in "aeiou" else 0
       for idx, char in enumerate(A)) )

Answer 2

Когда вы нажимаете гласный в строке, все подстроки, начинающиеся с этого гласного, «удивительны», так что вы можете просто посчитать их:

def solve(A):
            x = ['a', 'e','i','o', 'u', 'A', 'E', 'I', 'O', 'U']
            ans = 0

            for i in range(len(A)):
                if A[i] in x:
                    ans = (ans + len(A)-i)%10003
            return ans

Answer 3

Более общее решение состоит в том, чтобы найти все удивительные подстроки и затем посчитать их:

string = "pGpEusuCSWEaPOJmamlFAnIBgAJGtcJaMPFTLfUfkQKXeymydQsdWCTyEFjFgbSmknAmKYFHopWceEyCSumTyAFwhrLqQXbWnXSn"

amazing_substring_start = ['a','e','i','o','u','A','E','I','O','U']

amazing_substrings = []

for i in range(len(string)):
    if string[i] in amazing_substring_start:
        for j in range(len(string[i:])+1):
            amazing_substring = string[i:i+j]
            if amazing_substring!='':
                amazing_substrings += [amazing_substring]

print amazing_substrings,len(amazing_substrings)%10003

Answer 4

Когда вы ищете индекс элемента n = A.index(i), вы получаете индекс первого вхождения элемента.Используя enumerate, вы можете одновременно проходить по индексам и элементам.

def solve(A):
    x = ['a', 'e','i','o', 'u', 'A', 'E', 'I', 'O', 'U']
    y = []
    z = len(A)
    for n,i in enumerate(A):
        if i in x:
            m = z
            while m > n:
                y.append(A[n:m])
                m -= 1
    if y:
        return len(y)%10003
    else:
        return 0