Эта статья участвует в "Месяце тем Python", подробнее см.Ссылка на мероприятие
описывать
A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not.
Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.
Example 1:
Input: s = "YazaAay"
Output: "aAa"
Explanation: "aAa" is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear.
"aAa" is the longest nice substring.
Example 2:
Input: s = "Bb"
Output: "Bb"
Explanation: "Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring.
Example 3:
Input: s = "c"
Output: ""
Explanation: There are no nice substrings.
Example 4:
Input: s = "dDzeE"
Output: "dD"
Explanation: Both "dD" and "eE" are the longest nice substrings.
As there are multiple longest nice substrings, return "dD" since it occurs earlier.
Note:
1 <= s.length <= 100
s consists of uppercase and lowercase English letters.
Разобрать
По смыслу вопроса, заключается в том, чтобы найти самую длинную красивую строку, которая является подстрокой s и должна содержать одновременно прописную и строчную буквы определенной английской буквы. Используйте метод грубой силы для обхода всех возможных подстрок в двойном цикле, чтобы определить, хороша ли она, если да и длина больше, присвоить ее результату, а результат, полученный в конце обхода, и есть результат.
отвечать
class Solution(object):
def longestNiceSubstring(self, s):
"""
:type s: str
:rtype: str
"""
def isNice(string):
string_ = string.swapcase()
string_list = list(string_)
stringlist = list(string)
for c in stringlist:
if c not in string_list:
return False
return True
result = ''
for i in range(len(s)-1):
for j in range(i+1,len(s)):
tmp = s[i:j+1]
if isNice(tmp) and len(tmp)>len(result):
result = tmp
return result
результат операции
Runtime: 280 ms, faster than 20.59% of Python online submissions for Longest Nice Substring.
Memory Usage: 13.4 MB, less than 93.14% of Python online submissions for Longest Nice Substring.
Разобрать
Кроме того, вы можете использовать рекурсивный метод, чтобы найти некоторые символы в s и поместить их в список p. Верхний/нижний регистр этих символов не в s, что означает, что они не имеют возможности стать NiceSubstring, поэтому эти символы используются в качестве разделительной линии и делятся на два символа слева и справа.Если длина p в строке равна 0, это означает, что это NiceSubstring, и ее можно вернуть напрямую.Наконец, все символы Найденные NiceSubstring сортируются, вы можете найти самую старую и самую длинную NiceSubstring.
отвечать
class Solution(object):
def longestNiceSubstring(self, s):
"""
:type s: str
:rtype: str
"""
def discovery(s):
if len(s) < 2:
return ""
p = []
for i, ch in enumerate(s):
if ch.isupper() and ch.lower() not in s:
p.append(i)
if ch.islower() and ch.upper() not in s:
p.append(i)
if not p:
return s
else:
mid = (len(p)) // 2
left = s[:p[mid]]
right = s[p[mid]+1:]
return max(discovery(left),discovery(right), key=len)
return discovery(s)
результат операции
Runtime: 32 ms, faster than 68.37% of Python online submissions for Longest Nice Substring.
Memory Usage: 13.6 MB, less than 52.04% of Python online submissions for Longest Nice Substring.
Ссылка на оригинальное название:Lee TCO's.com/problems/ …
Ваша поддержка - моя самая большая мотивация