public static int editDistance()

in tools/automatic_query_fixer/src/main/java/com/google/cloud/bigquery/utils/queryfixer/util/StringUtil.java [79:118]

• 29 lines of code
• 7 McCabe index (conditional complexity)

  public static int editDistance(String word1, String word2, boolean caseSensitive) {
    if (!caseSensitive) {
      word1 = word1.toLowerCase();
      word2 = word2.toLowerCase();
    }

    int len1 = word1.length();
    int len2 = word2.length();

    // len1+1, len2+1, because finally return dp[len1][len2]
    int[][] dp = new int[len1 + 1][len2 + 1];

    for (int i = 0; i <= len1; i++) {
      dp[i][0] = i;
    }

    for (int j = 0; j <= len2; j++) {
      dp[0][j] = j;
    }

    // iterate though, and check last char
    for (int i = 0; i < len1; i++) {
      char c1 = word1.charAt(i);
      for (int j = 0; j < len2; j++) {
        char c2 = word2.charAt(j);

        // if last two chars equal
        if (c1 == c2) {
          // update dp value for +1 length
          dp[i + 1][j + 1] = dp[i][j];
        } else {
          int replace = dp[i][j] + 1;
          int insert = Math.min(dp[i][j + 1], dp[i + 1][j]) + 1;
          dp[i + 1][j + 1] = Math.min(replace, insert);
        }
      }
    }

    return dp[len1][len2];
  }