관리 메뉴

솜씨좋은장씨

[leetCode] 686. Repeated String Match (Python) 본문

Programming/코딩 1일 1문제

[leetCode] 686. Repeated String Match (Python)

솜씨좋은장씨 2020. 9. 24. 00:22
728x90
반응형

Given two strings a and b, return the minimum number of times you should repeat string a so that string b is a substring of it. If it is impossible for b​​​​​​ to be a substring of a after repeating it, return -1.

Notice: string "abc" repeated 0 times is "",  repeated 1 time is "abc" and repeated 2 times is "abcabc".

 

Example 1:

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

Example 2:

Input: a = "a", b = "aa"
Output: 2

Example 3:

Input: a = "a", b = "a"
Output: 1

Example 4:

Input: a = "abc", b = "wxyz"
Output: -1

Constraints:

  • 1 <= a.length <= 104
  • 1 <= b.length <= 104
  • a and b consist of lower-case English letters.

Solution

class Solution:
    def repeatedStringMatch(self, A: str, B: str) -> int:
        A_len = len(A)
        B_len = len(B)
        
        answer = B_len // A_len + 2
        temp = A * answer
        if B not in temp:
            return -1
        while B in A * (answer-1):
            answer = answer - 1
        return answer

 

SOMJANG/CODINGTEST_PRACTICE

1일 1문제 since 2020.02.07. Contribute to SOMJANG/CODINGTEST_PRACTICE development by creating an account on GitHub.

github.com

Comments