2

私の友人は私に次の問題を与えました：

Input: A matrix of letters and a word.
Output: The frequency of the word in the matrix assuming
  you can move left, right, up and down in the matrix to form the word.

例えば：

Input:
S E X Y
A S E A
A A X A
A A Y A
And word is SEXY.

Output:
4 (four times in matrix of letters)

これは問題を解決するための私のコードです:

package backtracking;

public class CountFrequency {
    private char[][] matrixOfLetter;
    private String word;
    private int n, m;
    private int lengthOfWord;
    private int[][] matrixCountFrequency;

    public CountFrequency(int n, int m, String word) {
        matrixOfLetter = new char[n][m];
        this.word = word;
        this.n = n;
        this.m = m;
        this.lengthOfWord = word.length();

        matrixCountFrequency = new int[n][m];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                matrixCountFrequency[i][j] = 0;
    }

    public static void main(String[] args) {
        CountFrequency countFrequency = new CountFrequency(4, 4, "SEXY");

        countFrequency.addMatrixOfLetter(0, 0, 'S');
        countFrequency.addMatrixOfLetter(0, 1, 'E');
        countFrequency.addMatrixOfLetter(0, 2, 'X');
        countFrequency.addMatrixOfLetter(0, 3, 'Y');
        countFrequency.addMatrixOfLetter(1, 0, 'A');
        countFrequency.addMatrixOfLetter(1, 1, 'S');
        countFrequency.addMatrixOfLetter(1, 2, 'E');
        countFrequency.addMatrixOfLetter(1, 3, 'A');
        countFrequency.addMatrixOfLetter(2, 0, 'A');
        countFrequency.addMatrixOfLetter(2, 1, 'A');
        countFrequency.addMatrixOfLetter(2, 2, 'X');
        countFrequency.addMatrixOfLetter(2, 3, 'A');
        countFrequency.addMatrixOfLetter(3, 0, 'A');
        countFrequency.addMatrixOfLetter(3, 1, 'A');
        countFrequency.addMatrixOfLetter(3, 2, 'Y');
        countFrequency.addMatrixOfLetter(3, 3, 'A');

        countFrequency.process();
        countFrequency.printResult();
    }

    public void addMatrixOfLetter(int i, int j, char c) {
        matrixOfLetter[i][j] = c;
    }

    public void process() {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                if (word.indexOf(matrixOfLetter[i][j]) == -1) {
                    matrixCountFrequency[i][j] = -1;
                    continue;
                }
                if (matrixOfLetter[i][j] == word.charAt(lengthOfWord - 1))
                    processWithLastChar(lengthOfWord - 1, i, j);
            }
    }

    public void processWithLastChar(int indexOfWord, int row, int col) {
        matrixCountFrequency[row][col] += 1;
        if (indexOfWord == 0)
            return;
        else {
            if (row - 1 >= 0) {
                if (matrixOfLetter[row - 1][col] == word
                        .charAt(indexOfWord - 1))
                    processWithLastChar(indexOfWord - 1, row - 1, col);
            }

            if (row + 1 < lengthOfWord) {
                if (matrixOfLetter[row + 1][col] == word
                        .charAt(indexOfWord - 1))
                    processWithLastChar(indexOfWord - 1, row + 1, col);
            }

            if (col - 1 >= 0) {
                if (matrixOfLetter[row][col - 1] == word
                        .charAt(indexOfWord - 1))
                    processWithLastChar(indexOfWord - 1, row, col - 1);
            }

            if (col + 1 < lengthOfWord) {
                if (matrixOfLetter[row][col + 1] == word
                        .charAt(indexOfWord - 1))
                    processWithLastChar(indexOfWord - 1, row, col + 1);
            }
        }
    }

    public void printResult() {
        int count = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                if (word.charAt(0) == matrixOfLetter[i][j])
                    count += matrixCountFrequency[i][j];
            }

        System.out.println("Frequency is : " + count);
    }
}

バックトラックアルゴリズムを使用しましたが、単語の最後の文字が表示されたときにのみバックトラックし、単語の右端にある文字が表示されたときに再びバックトラックします。

文字の頻度をカウントするためにカウンターのマトリックスを使用します。

その問題は動的計画法アルゴリズムで解決できますか?

または、より良いアイデアはありますか？

4

1 に答える 1

4

動的計画法で解決できます。これが最も理解しやすい解決策だと思います。

平行な 3 次元マトリックスを作成します。文字行列の次元がnxmで、検索する単語がL文字長の場合、 matrix を作成しますdp[n][m][L]。その文字を単語の文字としてdp[i][j][k]使用する方法をいくつ見つけたかを保存します。initial[i][j]k

あなたは を持ってdp[i][j][k] = sum(dp[i+delta1][j + delta2][k + 1])い{delta1, delta2} in {{0, 1},{0, -1}, {1, 0}, {-1, 0}}ます。再帰の一番下はdelta[i][j][L - 1] = (initial[i][j] == word[L - 1]).

dp[i][j][l - 1]可能なすべての i と jを合計すると、最終結果が得られます。

うまくいけば、これはあなたを助けます。

編集

最初の解決策で愚かな提案をしたことを告白しなければなりません。私が提案する動的な解決策は、私が使用した文字を考慮に入れていません。したがって、マトリックスの場合

XXXX
XABX
XXXX

そして、文字列 ABAB 私のアルゴリズムは 1 のカウントを返します。A から B に移動し、A に戻り、B に戻ります。これはおそらく、必要なものとは異なります。

残念ながら、動的なアプローチでは、既にアクセスしたものを追跡することは簡単ではありません。今では、バックトラックの方が問題に適していると思い始めています。

ちなみに、ソリューションでもそれを考慮していませんが、バックトラック中にアクセスしたものを追跡する方がはるかに簡単です。また、バックトラックはメモリとパフォーマンスの面でより効率的だと思います。

于 2013-05-09T11:26:34.133 に答える