행렬의 회문 경로 수

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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)입니다.