[Lint Code] Split String

[Lint Code] Split String

문제 : 문자열이 주어졌을 때 한 개의 문자 혹은 두 개의 문자로 구성된 문자열들로 구성할 수 있는 전체 경우를 구하시오

[예시]

Input -> "123"
 
Output -> [["1", "2", "3"], ["12", "3"], ["1", "23"]]

[풀이]

이 문제는 [start:start+1]과 [start:start+2]의 경우를 DFS를 이용하여 모든 경우의 수를 탐색하여 풀면 된다.

[코드]

class Solution:
    """
    @param: : a string to be split
    @return: all possible split string array
    """
 
    def func(self, s, start, end, row, matrix):
        # 기저사례: end가 문자열 s의 길이면 matrix 배열에 추가 후 종료
        if(end == len(s)):
            matrix.append([])
            for i in range(len(row)):
                matrix[len(matrix)-1].append(row[i])
            return
 
        # end+1이 len(s) 보다 작다면 : case one character
        if end+1 <= len(s):
            # s[end:end+1]를 row에 추가후 재귀호출
            row.append(s[end:end+1])
            self.func(s, end, end+1, row, matrix)
            # s[end:end+1]에 값을 row 배열에서 pop
            row.pop(len(row)-1)
 
        # end+2이 len(s) 보다 작다면 : case two character
        if end+2 <= len(s):
            # s[end:end+2]를 row에 추가후 재귀호출
            row.append(s[end:end+2])
            self.func(s, end, end+2, row, matrix)
 
    def splitString(self, s):
        # write your code here
 
        matrix = []
 
        row = []
 
        # s의 문자열의 길이가 1개이상일 경우 s[0]번째를 row에 넣고 재귀함수 호출 시작
        if len(s) >= 1:
            row.append(s[0:1])
            self.func(s, 0, 1, row, matrix)
 
        # s의 문자열의 길이가 2개이상일 경우 s[0]과 s[1]이 합쳐진 문자열을 row에 넣고 재귀함수 호출 시작
        if len(s) >= 2:
            row = []
            row.append(s[0:2])
            self.func(s, 0, 2, row, matrix)
 
        return matrix