• Home
  • About
    • JOOS photo

      JOOS

      Joos's blog

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

[leet_code] 395. Longest Substring with At Least K Repeating Characters with python3

09 Aug 2019

Reading time ~1 minute

문제 : https://leetcode.com/problems/repeated-dna-sequences/

목표:

  • 길이가 10인 sub_string 중 개수가 2 이상인 sub_string을 구하라

    조건:

  • 없다

    solution 설명 :

  • O(N)
  • brute force로 모든 sub_string을 다 구한다.
  • 그것을 defaultdict에 넣고 개수를 센다.
from collections import defaultdict

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        counts = defaultdict(lambda: 0) # Default 값을 0으로 설정합니다.
        ans = set()
        for i in range(len(s)-9):
            sub_string = s[i:i+10]
            counts[sub_string] += 1
            if counts[sub_string] > 1: ans.add(sub_string)
        return ans


algorithmleet_codepython Share Tweet +1