.leetcode(647. Palindromic Substrings)

문제

https://leetcode.com/problems/palindromic-substrings/

문제 풀기 전

1. brute force로 풀었다.

직접 푼 풀이

소요시간: 10분(19:54 ~ 20:04)

//visted를 이용해 recursion
class Solution {
    private int[][] visited;
    public boolean searchMatrix(int[][] matrix, int target) {
        visited = new int[matrix.length][matrix[0].length];

        for (int i=0; i<matrix.length; i++) {
            for (int j=0; j<matrix[i].length; j++) {
                visited[i][j] = -1;
            }
        }   

        return find(matrix, 0, 0, target) == 1;
    }

    private int find(int[][] matrix, int i, int j, int target) {
        if (i<0 || matrix.length<=i || j<0 || matrix[i].length<=j) {
            return 0;
        }

        if (visited[i][j] != -1) {
            return visited[i][j];
        }

        int current = matrix[i][j];
        if (current > target) {
            return 0;
        } else if (current == target) {
            return 1;
        }


        return visited[i][j] = find(matrix, i+1, j, target) | find(matrix, i, j+1, target);
    }
}

느낀점

1. 내가 푼 방식이 binarySearch와 유사한것으로 보인다.
2. divide and conquer로 푸는 방법이 있다.
3. 가장 기막힌 풀이는 좁혀가는 방법이었다.

솔루션 공부 후 추가로 푼 풀이

# divide and conquer 로 푼 방법
class Solution {
    private int[][] gmatrix;
    private int gtarget;
    public boolean searchMatrix(int[][] matrix, int target) {
        gmatrix = matrix;
        gtarget = target;

        return dc(0, matrix.length-1, 0, matrix[0].length-1);
    }

    private boolean dc(int left, int right, int up, int down) {
        if (left>right || up>down) {
            return false;
        }

        int mid = (left+right)/2;

        int temp = up;
        while(temp<=down && gmatrix[mid][temp] <= gtarget) {
            if (gmatrix[mid][temp] == gtarget) {
                return true;
            }
            temp++;
        }

        return dc(left, mid-1, temp, down) || dc(mid+1, right, up, temp-1);
    }
}

# 좁혀가기
class Solution {
    private int[][] gmatrix;
    private int gtarget;
    public boolean searchMatrix(int[][] matrix, int target) {

        int i=0;
        int j=matrix[0].length-1;
        while(0<=i && 0<=j && i<matrix.length && j < matrix[0].length) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
            } else if (matrix[i][j] > target) {
                j--;
            }
        }

        return false;
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)

나중에다시한번

• 풀이를 3가지 방식으로 풀어보기