String

Updated: 2021-12-15

Palindrome

while (lo < hi) {
    if s[lo] != s[hi]
    lo++;
    hi--;
}

Reverse a string

void reverse(char* str)
{
    char *low = str,  *high = str;
    while (*high != '\0') {
        high++;
    }
    high--;
    while (low < high){
        char tmp = *low;
        *low++ = *high;
        *high-- = tmp;
    }
}

Levenshtein Distance

public static int LevenshteinDistance(char[] a, char[] b){

    int [][] cnt = new int[a.length + 1][b.length + 1];
    for (int i = 0; i <= a.length; i++) {
        cnt[i][0] = i;
    }
    for (int i = 0; i <= b.length; i++) {
        cnt[0][i] = i;
    }
    for (int i = 1; i <= a.length; i++) {
        for (int j = 1; j<= b.length; j++){
            if (a[i-1] == b[j-1])
                cnt[i][j] = cnt[i-1][j-1];
            else {
                int smallest = cnt[i-1][j-1] + 1;
                if (cnt[i-1][j] + 1 < smallest)
                    smallest = cnt[i-1][j] + 1;
                if (cnt[i][j-1] + 1 < smallest)
                    smallest = cnt[i][j-1] + 1;
                cnt[i][j] = smallest;
            }
        }
    }
    return cnt[a.length][b.length];
}