title: Edit Distance solution for Large Strings
body: <p>I'm trying to solve the <a href="http://en.wikipedia.org/wiki/Edit_distance" rel="nofollow">edit distance</a> problem. the code I've been using is below.</p>
  
  <pre><code> public static int minDistance(String word1, String word2) {
      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 &lt;= len1; i++) {
          dp[i][0] = i;
      }
  
      for (int j = 0; j &lt;= len2; j++) {
          dp[0][j] = j;
      }
  
      //iterate though, and check last char
      for (int i = 0; i &lt; len1; i++) {
          char c1 = word1.charAt(i);
          for (int j = 0; j &lt; 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 = dp[i][j + 1] + 1  ;
                  int delete = dp[i + 1][j] + 1 ;
  
  
                  int min = replace &gt; insert ? insert : replace;
                  min = delete &gt; min ? min : delete;
                  dp[i + 1][j + 1] = min;
              }
          }
      }
  
      return dp[len1][len2];
  }
  </code></pre>
  
  <p>It's a DP approach. The problem it since it use a 2D array <strong>we cant solve this problem using above method for large strings</strong>. Ex: String length > 100000.</p>
  
  <p>So Is there anyway to modify this algorithm to overcome that difficulty ?</p>
  
  <p>NOTE: 
  The above code will accurately solve the Edit Distance problem for small strings. (which has length below 1000 or near)</p>
  
  <p>As you can see in the code it uses a Java 2D Array "dp[][]" . So we can't initialize a 2D array for large rows and columns.</p>
  
  <p>Ex : If i need to check 2  strings whose lengths are more than 100000</p>
  
  <pre><code>int[][] dp = new int[len1 + 1][len2 + 1];
  </code></pre>
  
  <p>the above will be </p>
  
  <pre><code>int[][] dp = new int[100000][100000];
  </code></pre>
  
  <p>So it will give a stackOverflow error.</p>
  
  <p>So the above program only good for small length Strings. 
  What I'm asking is , Is there any way to solve this problem for large strings(length > 100000) efficiently in java. </p>