행렬의 회문 경로 수

난이도 하드
자주 묻는 질문 Apple 코드네이션 Facebook 광신자 구글
동적 프로그래밍 매트릭스 팔린 드롬조회수 67

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

소문자 영어 알파벳을 포함하는 XNUMX 차원 행렬이 주어졌고 그 안에 회문 경로의 수를 세어야합니다. 회문 경로는 회문 속성을 따르는 경로 일뿐입니다. 뒤집었을 때 초기 단어와 동일하게 유지되는 단어를 회문이라고합니다. 초기 지점에서 목적지까지의 경로 수를 계산해야합니다. 시작 지점은 왼쪽 상단 셀이고 목적지는 오른쪽 하단 모서리입니다. 이동 방향에도 조건이 있습니다. 현재 셀에서 오른쪽과 아래쪽 방향으로 이동합니다.

행렬의 회문 경로 수

Matrix = { a a b

           a z a

           b a a }
6

설명 : 주어진 행렬에서 회문 경로를 얻는 6 가지 방법이 있습니다. 초기 지점 (0,0)에서 (0,1) 및 (1,0)으로 만 이동할 수 있기 때문입니다.

네 가지 경로는 aabaa, aazaa, aazaa, aabaa, aazaa, aazaa입니다. 두 경로는 비슷합니다. 주어진 행렬이 주 대각선에 대해 대칭이기 때문입니다. 그 이유는 두 개의 유사한 회문 경로가 있기 때문입니다.

{a}
1

설명 : 회문이기도 한 단일 경로 "a"만 있기 때문입니다. 답은 1입니다.

행렬 문제에서 회문 경로 수에 대한 접근 방식

순진한 접근

이 문제에서는 재귀를 사용하여 가능한 모든 경로 시퀀스를 찾은 다음 경로가 회문인지 확인합니다. 이전에 언급 된 접근 방식은 충분히 효율적이지 않은 역 추적을 사용했습니다. 역 추적은 가능한 모든 솔루션을 생성하기 때문입니다. 우리는 이러한 모든 솔루션을 확인합니다. 회문. 이것은 충분히 효율적이지 않기 때문에 초기 지점과 목적지에서 경로에 알파벳에 대한 두 개의 변수를 유지합니다.

효율적인 접근

이제 알고리즘을 요약 할 수 있습니다. 우리는 셀을 저장하는 두 개의 변수를 사용합니다. 이 두 개의 저장된 변수는 회문 속성을 충족하기 위해 동일해야합니다. 알파벳이 같으면 앞으로 나아갑니다. 앞으로 나아가는 것은 가능한 모든 방향에서 하위 문제에 대해 재귀 호출을한다는 것을 의미했습니다. 재귀 적 솔루션이있을 때마다. 우리는 생각할 수 있습니다 동적 프로그래밍 중복되는 하위 문제가있는 경우. 몇 가지 하위 문제를 여러 번 해결하므로 결과를 저장하는 것이 좋습니다. 하위 문제의 결과를 저장하기 위해 맵을 사용할 수 있습니다. 시작 및 종료 셀의 인덱스는 맵의 키 역할을합니다. 이것이 2D 배열에서 회문 경로의 수를 찾는 방법입니다.

행렬 문제의 회문 경로 수에 대한 코드

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

// checks if index i,j is valid or not (lies inside matrix or not)
bool isValid (int n, int m, int i, int j) {
    return !(i < 0 || i >= n || j < 0 || j >= m);
}

// return number of palindromic paths in matrix
int solvePalindromicPaths(vector<vector<char>> &matrix, int startRow, int startCol, int endRow, int endCol, map<pair<pair<int,int>,pair<int,int>>,int> &dp) {
    int n = matrix.size(), m = matrix[0].size();
    
    // check if start and end cell indices are valid (are inside matrix)
    if (!isValid(n, m, startRow, startCol) || !isValid(n, m, endRow, endCol))
        return 0;
    // if start indices are after end indices, they can not meet in middle
    if (startRow > endRow || startCol > endCol)
    return 0;
    // if path does not follow palindromic property
    if (matrix[startRow][startCol] != matrix[endRow][endCol])
        return 0;
    // indices are adjacent to each other
    if (abs((startRow - endRow) + (startCol - endCol)) <= 1)
        return 1;
    // store indices as pair, since our map is using indices as key
    pair<pair<int,int>,pair<int,int>> indices = pair<pair<int,int>,pair<int,int>>
                                                (pair<int,int>(startRow, startCol), pair<int,int>(endRow, endCol));
                                                
    // if sub-problem has alredy been calculated
    if(dp.count(indices))
        return dp[indices];
        
    // if not calculated, calculate result by recursively calling in all directions
    int countOfPalindromicPaths = 0;
    countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow + 1, startCol, endRow - 1, endCol, dp);
    countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow + 1, startCol, endRow, endCol - 1, dp);
    countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow, startCol + 1, endRow - 1, endCol, dp);
    countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow, startCol + 1, endRow, endCol - 1, dp);
    
    // store and return the result
    return dp[indices] = countOfPalindromicPaths;
}

int main() {
    int t;cin>>t;
    while(t--){
        int n,m;cin>>n>>m;
        vector<vector<char>> matrix(n, vector<char>(m));
        map<pair<pair<int,int>,pair<int,int>>,int> dp;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
            cin>>matrix[i][j];
        }
        cout<<solvePalindromicPaths(matrix, 0, 0, n-1, m-1, dp)<<endl;
    }
}
2
2 2
a b
b a
3 3
a a b
a z a
b a a
2
6

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Indices {
    private int startRow;
    private int startCol;
    private int endRow;
    private int endCol;

    public Indices(int startRow, int startCol, int endRow, int endCol) {
        this.startRow = startRow;
        this.startCol = startCol;
        this.endRow = endRow;
        this.endCol = endCol;
    }
}

public class Main {

    // checks if index i,j is valid or not (lies inside matrix or not)
    static boolean isValid (int n, int m, int i, int j) {
        return !(i < 0 || i >= n || j < 0 || j >= m);
    }

    // return number of palindromic paths in matrix
    static int solvePalindromicPaths(char[][] matrix, int startRow, int startCol, int endRow, int endCol, int n, int m, HashMap<Indices, Integer> dp) {
        // check if start and end cell indices are valid (are inside matrix)
        if (!isValid(n, m, startRow, startCol) || !isValid(n, m, endRow, endCol))
            return 0;
        // if start indices are after end indices, they can not meet in middle
        if (startRow > endRow || startCol > endCol)
            return 0;
        // if path does not follow palindromic property
        if (matrix[startRow][startCol] != matrix[endRow][endCol])
            return 0;
        // indices are adjacent to each other
        if (Math.abs((startRow - endRow) + (startCol - endCol)) <= 1)
            return 1;
        // create an instance of indices with current values, since our map is using indices as key
        Indices indices = new Indices(startRow, startCol, endRow, endCol);

        // if sub-problem has alredy been calculated
        if(dp.containsKey(indices))
            return dp.get(indices);

        // if not calculated, calculate result by recursively calling in all directions
        int countOfPalindromicPaths = 0;
        countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow + 1, startCol, endRow - 1, endCol, n, m, dp);
        countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow + 1, startCol, endRow, endCol - 1, n, m, dp);
        countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow, startCol + 1, endRow - 1, endCol, n, m, dp);
        countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow, startCol + 1, endRow, endCol - 1, n, m, dp);

        // store and return the result
        dp.put(indices, countOfPalindromicPaths);
        return countOfPalindromicPaths;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- > 0){
            int n = sc.nextInt();
            int m = sc.nextInt();
            char matrix[][] = new char[n][m];

            HashMap<Indices, Integer> dp = new HashMap<>();
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++) {
                    matrix[i][j] = sc.next().charAt(0);
                }
            }
            System.out.println(solvePalindromicPaths(matrix, 0, 0, n-1, m-1, n, m, dp));
        }
    }
}
2
2 2
a b
b a
3 3
a a b
a z a
b a a
2
6

복잡성 분석

시간 복잡성 : O (N * M)

하위 문제의 결과를 저장하고 있기 때문입니다. 총 N * M 상태가 있기 때문입니다. 우리는 O (N * M)의 시간 복잡도를 가지고 있는데, 이는 행렬 문제에서 회문 경로의 수에 다항식 시간 복잡도가 있음을 의미합니다.

공간 복잡성 : O (N * M)

N * M 상태 만 있기 때문에 공간 복잡도는 O (N * M)입니다.

균열 시스템 설계 인터뷰
Translate »