title: Optimizing and improving the speed of a recursive algorithm that compares strings
body: <p>The following algorithm works as such: Given two strings, return true if the strings are equal to each other regardless of their vowels.</p>
  <p>&quot;water&quot; and &quot;wtr&quot; = true</p>
  <p>&quot;helloo&quot; and &quot;hll&quot; = true</p>
  <p>&quot;violinn&quot; and &quot;vln&quot; = false</p>
  <p>There are some parameters set in place.  It must be solved recursively, not iteratively.  Also, simply removing the vowels from both strings and comparing them is not allowed.</p>
  <p>This is a program I wrote to solve this problem (call <code>isStringEqual(&quot;water&quot;, &quot;wtr&quot;)</code>):</p>
  <p>This, given a string and a starting index, will call itself until it has found the index of a consonant.  If no consonants are present, then it returns -1.</p>
  <pre class="lang-java prettyprint-override"><code>    static int findNonVowel(String str, int strIndex) {
  
          if (str.length() == strIndex) return -1;
  
          if (&quot;aeiouAEIOU&quot;.indexOf(str.charAt(strIndex)) == -1) return strIndex;
  
          strIndex++;
          return findNonVowel(str, strIndex);
      }
  </code></pre>
  <p>Now, this is the main part of the solution.</p>
  <pre class="lang-java prettyprint-override"><code>    static boolean isStringEqual(String strA, String strB) {
          return doIsStringEqual(strA, strB, 0, 0);
      }
  
      static boolean doIsStringEqual(String strA, String strB, int strAIndex, int strBIndex) {
          if (strA.length() &gt; strB.length() &amp;&amp; strB.length() == strBIndex &amp;&amp; findNonVowel(strA, strAIndex) != -1)         
              return false;
  
          if (strB.length() &gt; strB.length() &amp;&amp; strA.length() == strAIndex &amp;&amp; findNonVowel(strB, strBIndex) != -1)         
              return false;
  
          if (strA.length() == strAIndex || strB.length() == strBIndex) return true;
  
          if (strA.charAt(strAIndex) != strB.charAt(strBIndex)) {
              strAIndex = findNonVowel(strA, strAIndex);
              strBIndex = findNonVowel(strB, strBIndex);
  
              if (strA.charAt(strAIndex) != strB.charAt(strBIndex) &amp;&amp; (strAIndex != -1  &amp;&amp; strBIndex != -1)) {
                  return false;
              }
          }
  
          strAIndex++; strBIndex++;
          return doIsStringEqual(strA, strB, strAIndex, strBIndex);
      }
  </code></pre>
  <p>First, we check if one of either of the strings are larger than the other and that, through recursion, they have exceeded the length of the other string.  This is to prevent false positives like this &quot;violinn&quot; and &quot;vln&quot; but still allows for &quot;violiniii&quot; and &quot;vln&quot; through <code>findNonVowel</code>.</p>
  <p>If the two characters found don't match each other we get the index of the nearest consonant for each, and compare those.  If they still don't equal each other, and neither strings are all vowels from the starting index then the strings don't equal.</p>
  <p>I'm looking for a more memory efficient solution to this problem.  I've looked into substrings, but from my understanding this would be much slower as they instantiate a new string with every recursive call, whereas this is simply recalling that same method.</p>
  <p>I'd also be open to any improvements that could be made to the algorithm itself, whether it's simplifying it, or trimming off any boilerplate.</p>