• 注册
    • 查看作者
    • 领扣: 647题 子串字谜

      647. Find All Anagrams in a String

      Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

      Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 40,000.

      The order of output does not matter.

      Example

      Example 1:

      Input : s =  "cbaebabacd", p = "abc"
      Output : [0, 6]
      Explanation : 
      The substring with start index = 0 is "cba", which is an anagram of "abc".
      The substring with start index = 6 is "bac", which is an anagram of "abc".

      class Solution:
          """
          @param s: a string
          @param p: a string
          @return: a list of index
          """
          def findAnagrams(self, s, p):
              # write your code here
              result = []
              possible ={}
              windows= {}
              length = len(p)
              for each in range(len(p)):
                  if possible.get(p[each]):
                      possible[p[each]] =  possible.get(p[each]) +1
                  else:
                      possible[p[each]] = 1
              print (possible)
              
              
              for each in s[0:length]:
                  if windows.get(each) is not None :
                      windows[each] =  windows.get(each) +1
                  else:
                      windows[each] = 1
                              
              for i in range(len(s)-length+1):
                  print('window = ' + str(windows))
                  print('possible = ' + str(possible))
                  if windows == possible:
                      result.append(i)
                  print(s[i])
                  print(windows.get(s[i]))
                  if windows.get(s[i]) == 1:
                      windows.pop(s[i])
                  else:
                      
                      windows[s[i]] =  windows.get(s[i]) -1
                  if i+length < len(s) and windows.get(s[i+length]):
                      windows[s[i+length]] =  windows.get(s[i+length]) +1
                      
                  elif i+length< len(s):
                      windows[s[i+length]] = 1
              return result

      领扣对结果审查更加严格 在leetcode上可以过的 方法 均超时

      class Solution:
          """
          @param s: a string
          @param p: a string
          @return: a list of index
          """
          def findAnagrams(self, s, p):
              # write your code here
              result = []
              length = len(p)
              #print (possible)
              
              
              p = ''.join(sorted(p))
              for i in range(len(s)-length+1):
                  #print ("p = " + str(p))
                  #print ("s[i:length+i] = " + str(''.join(sorted(s[i:length+i]))))
                  if ''.join(sorted(s[i:length+i])) == p:
                      
                      result.append(i)
              return result

      class Solution:
          """
          @param s: a string
          @param p: a string
          @return: a list of index
          """
          def findAnagrams(self, s, p):
              # write your code here
              result = []
              possible ={}
              for each in range(len(p)):
                  if possible.get(p[each]):
                      possible[p[each]] =  possible.get(p[each]) +1
                  else:
                      possible[p[each]] = 1
              #print (possible)
              
              
              length = len(p)
              for i in range(len(s)):
                  temp = possible.copy()
                  for each in s[i:i+length]:
                      print (temp.get(each))
                      if temp.get(each) is not None and temp[each]> 1:
                          temp[each]= temp.get(each) - 1
                      elif temp.get(each) is not None:
                          temp.pop(each)
                  if len(temp) == 0:
                      result.append(i)
              return result

      原因是其中有一个p等于10001个字符 直接超出array大小 且不能sort

      Input
      "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa ...

       Input Data

      Expected

      [0,10001]

      纽约州·法拉盛
    • 0
    • 0
    • 0
    • 518
    • 请登录之后再进行评论

      登录
    • 做任务