code: public static int damerau(char[] x, char[] y) {
          // switch parameters to use the shorter one as y to save space.
          if (x.length < y.length) {
              char[] swap = x;
              x = y;
              y = swap;
          }
  
          int[][] d = new int[3][y.length + 1];
  
          for (int j = 0; j <= y.length; j++) {
              d[1][j] = j;
          }
  
          for (int i = 1; i <= x.length; i++) {
              d[2][0] = i;
  
              for (int j = 1; j <= y.length; j++) {
                  int cost = x[i-1] == y[j-1] ? 0 : 1;
                  d[2][j] = Math.min(
                          d[1][j] + 1,       // deletion
                          d[2][j-1] + 1,       // insertion
                          d[1][j-1] + cost); // substitution
  
                  if (i > 1 && j > 1) {
                      if (x[i-1] == y[j-2] && x[i-2] == y[j-1])
                          d[2][j] = Math.min(d[2][j], d[0][j-2] + cost);   // damerau
                  }
              }
  
              int[] swap = d[0];
              d[0] = d[1];
              d[1] = d[2];
              d[2] = swap;
          }
  
          return d[1][y.length];
      }
docs: Damerau-Levenshtein distance between two strings allows insertion,
  deletion, substitution, or transposition of characters.
  O(mn) time and O(n) space. Multi-thread safe.