title: Possible to have different Longest Common Subsequence for same pair of Strings?
body: <p><strong>I have two input strings:</strong></p>
  <p>String1 = <code>3 9 8 3 9 7 9 7 0</code><br>
  String2 = <code>3 3 9 9 9 1 7 2 0</code></p>
  <p>Now, If I assess <strong>Left-To-Right</strong>, then LCS obtained : <code>3 3 9 9 7 0</code><br>
  But, If I assess <strong>Right-To-Left</strong>, then another possible LCS: <code>3 9 9 9 7 0</code></p>
  <p>Here's a picture to explain it (hopefully) better:</p>
  <p><a href="https://i.stack.imgur.com/dHU5m.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/dHU5m.png" alt="enter image description here" /></a></p>
  <p><strong>I wanted to understand if this is normal, or am I making a mistake ?</strong></p>
  <p>my code for generating LCS is below, which gives the Right-To-Left scenario output:</p>
  <pre><code>private static String[][] memo; // memoization
  
  public static String lcsMemoized(String[] p, String[] q, int pLen, int qLen) {
      String result = &quot;&quot;;
      // base case
      if (pLen == 0 || qLen == 0) return &quot;&quot;;
      else if (memo[pLen][qLen] != null) return memo[pLen][qLen];
      else if (p[pLen - 1].equals(q[qLen - 1])) {
          // common last character
          result = lcsMemoized(p, q, pLen - 1, qLen - 1) + p[pLen - 1];
      } else {
          String op1 = lcsMemoized(p, q, pLen - 1, qLen);
          String op2 = lcsMemoized(p, q, pLen, qLen - 1);
          if (op2.length() &gt; op1.length()) result = op2;
          else result = op1;
      }
      memo[pLen][qLen] = result;
      return result;
  }
  </code></pre>