Previously accepted solution exceeding time limit now


  • 0
    D

    My solution to this problem was accepted previously, but now it's exceeding time limit. Can someone tell me what changed in this problem?

    Here's my solution:

    public class Solution {
        public int minDistance(String word1, String word2) {
            int m = word1.length();
            int n = word2.length();
            int[][] D = new int[m + 1][n + 1];
            int i,j;
            D[0][0] = 0;
            for (i = 1; i <= m; i++) {
                D[i][0] = i;
            }
            for (j = 1; j <= n; j++) {
                D[0][j] = j;
            }
            
            for (i = 1; i <= m; i++) {
                for (j = 1; j <= n; j++) {
                    D[i][j] = Math.min(Integer.MAX_VALUE, D[i][j - 1] + 1);
                    D[i][j] = Math.min(D[i][j], D[i - 1][j] + 1);
                    if (word1.charAt(i - 1) == word2.charAt(j - 1))
                        D[i][j] = Math.min(D[i][j], D[i - 1][j - 1]);
                    else 
                        D[i][j] = Math.min(D[i][j], D[i - 1][j - 1] + 1);
                }
            }
            return D[m][n];
        }
    }
    

    It's TLE-ing for the test case:

    "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef"
    "bcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefg"

  • 0

    This issue had just been fixed. Your solution should be accepted now


  • 0
    D

    I think a similar problem exists on the problem "One Edit Distance". Can you take a look at that ?


  • 0

    I've tested on "One Edit Distance" and it works alright. The reason you get Time Limit Exceeded is because your algorithm is not efficient enough. The expected time complexity is O(n).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.