[C] 8ms, O(m*n) time, O(n) space


  • 0
    G
    //8ms
    int minDistance(char* word1, char* word2) {
        const int ALEN = (!word1 || !(*word1)) ? 0 : strlen(word1);
        const int BLEN = (!word2 || !(*word2)) ? 0 : strlen(word2);
    
        int c[ALEN + 1][2];
        int i, j;
    
        for (i = 0; i <= ALEN; i++) c[i][0] = i;
    
        int cur = 0, v;
        for (j = 1; j <= BLEN; j++) {
            int ch = word2[j - 1];
            cur = !cur;
            c[0][cur] = j;
            for (i = 1; i <= ALEN; i++) {
                v = c[i - 1][!cur] + (word1[i - 1] != ch);
                if (v > c[i - 1][cur] + 1) v = c[i - 1][cur] + 1;
                if (v > c[i][!cur] + 1) v = c[i][!cur] + 1;
                c[i][cur] = v;
            }
        }
    
        #ifdef MY_UNIT_TEST
        printf("c[%d]: [%3d", ALEN + 1, c[0][cur]);
        for (i = 1; i <= ALEN; i++) {
            printf(",%3d", c[i][cur]);
        }
        printf("]\n");
        #endif
        return c[ALEN][cur];
    }

  • 0
    G
    //12ms, O(m*n) time, O(m*n) space
    int minDistance(char* word1, char* word2) {
        const int ALEN = (!word1 || !(*word1)) ? 0 : strlen(word1);
        const int BLEN = (!word2 || !(*word2)) ? 0 : strlen(word2);
    
        int c[ALEN + 1][BLEN + 1];
        int i, j;
    
        for (i = 0; i <= ALEN; i++) c[i][0] = i;
        for (j = 1; j <= BLEN; j++) c[0][j] = j;
        for (i = 1; i <= ALEN; i++) {
            int ch = word1[i - 1];
            for (j = 1; j <= BLEN; j++) {
                int v, v1, v2;
                v = c[i - 1][j - 1] + (ch != word2[j - 1]);
                v1 = (c[i - 1][j] + 1);
                if (v > v1) v = v1;
                v2 = (c[i][j - 1] + 1);
                if (v > v2) v = v2;
                c[i][j] = v;
            }
        }
    
        #ifdef MY_UNIT_TEST
        printf("c[%d][%d]:\n", ALEN + 1, BLEN + 1);
        printf("      %3d", 0);
        for (j = 1; j <= BLEN; j++) {
            printf(" %3d", j);
        }
        printf("\n");
        for (i = 0; i <= ALEN; i++) {
            printf("%3d: [%3d", i, c[i][0]);
            for (j = 1; j <= BLEN; j++) {
                printf(",%3d", c[i][j]);
            }
            printf("]\n");
        }
        #endif
        return c[ALEN][BLEN];
    }

  • 0
    G
    int minDistance(char* word1, char* word2) {
        const int N1 = word1 ? strlen(word1) : 0;
        const int N2 = word2 ? strlen(word2) : 0;
        if (!N1 || !N2) return (N2 + N1);
        int c[N1 + 1];
        int i, j, prev_i_1, t1, t2;
        for (i = 0; i <= N1; i++) c[i] = i;
        for (j = 1; j <= N2; j++) {
            for (i = 1, prev_i_1 = c[0], c[0] = j; i <= N1; i++) {
                t1 = prev_i_1 + (word1[i - 1] != word2[j - 1]);
                prev_i_1 = c[i];
                t2 = (c[i] > c[i - 1]) ? c[i - 1] : c[i];
                t2++;
                c[i] = (t1 < t2) ? t1 : t2;
            }
        }
        return c[N1];
    }

Log in to reply
 

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