Python에서 문자열을 분할하는 여러 가지 방법을 찾는 프로그램

<시간/>

이진 문자열 s가 있다고 가정하면 s를 3개의 비어 있지 않은 문자열 s1, s2, s3으로 분할하여 (s1 연결 s2 연결 s3 =s)와 같이 할 수 있습니다. s1, s2, s3에서 문자 '1'의 수가 동일하도록 s를 분할할 수 있는 방법의 수를 찾아야 합니다. 답변이 매우 클 수 있으므로 답변 모드 10^9+7을 반환합니다.

따라서 입력이 s ="11101011"과 같으면 "11 | 1010 | 11" 및 "11 | 101 | 011"과 같이 나눌 수 있으므로 출력은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

count :=s에 있는 1의 수를 셉니다.
m :=10^9 + 7
ans :=크기가 2이고 0으로 채워지는 배열
카운트 모드 3이 0과 같지 않으면
- 0을 반환
그렇지 않으면 count가 0과 같을 때
- return(n은 s -1의 크기이고 r은 2인 nCr) mod m
왼쪽 :=0
오른쪽 :=s의 크기 - 1
cum_s :=0, cum_e :=0
cum_s <=count/3의 몫 또는 cum_e <=count/3의 몫인 동안 do
- s[left]가 "1"과 같으면
  - cum_s :=cum_s + 1
- s[right]가 "1"과 같으면
  - cum_e :=cum_e + 1
- cum_s가 count/3의 몫과 같으면
  - ans[0] :=ans[0] + 1
- cum_e가 count/3의 몫과 같으면
  - ans[1] :=ans[1] + 1
- 왼쪽 :=왼쪽 + 1
- 오른쪽 :=오른쪽 - 1
반환(ans[0]*ans[1]) 모드 m

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시

def solve(s):
   count = s.count("1")
   m = 10**9 + 7
   ans = [0, 0]
   if count % 3 != 0:
      return 0
   elif count == 0:
      return comb(len(s)-1,2) % m
   left = 0
   right = len(s)-1
   cum_s = 0
   cum_e = 0
   while(cum_s <= count//3 or cum_e <= count//3):
      if s[left] == "1":
         cum_s+=1
      if s[right] == "1":
         cum_e+=1
      if cum_s == count//3:
         ans[0]+=1
      if cum_e == count//3:
         ans[1]+=1
      left += 1
      right -= 1
   return (ans[0]*ans[1]) % m
s = "11101011"
print(solve(s))

입력

"11101011"