1
\$\begingroup\$

Say you have two strings: exp->aaccbb comp-> aa2bb

This example will return true as there are 2 chars between aa and bb. I have written this code snippet and am wondering if there is a better way do solve this problem and if I am missing any edge cases.

Also, what would be the fastest way to solve this problem with respect to time/place complexity? The solution is a 2 pointer approach with linear complexity. Follow up -> either side can have compressions or both at the same time.

const isNumber = (ch)=>{
  return Number(ch) == ch
}

const isExp = (exp, comp)=>{
  let i=j=0;


  while(i<exp.length && j<comp.length){
    if(comp[j] !== exp[i] && !isNumber(comp[j])){
      return false
    }
    else if(isNumber(comp[j])){

     let currentCompIdx = j;

     /*Find consexutive numbers*/
      while(isNumber(comp[currentCompIdx+1]))currentCompIdx++;

      /*Get Number from the compressed string*/
      const moveIndexBy = Number(comp.slice(j,currentCompIdx+1));
            /*set j pointer to index after the number*/
            j=currentCompIdx+1;

      /*Check if the letters after number is same*/
      if(comp[j] !== exp[i+moveIndexBy]){
        return false
      }
     i++;      
     j++;

    }
    else{
      i++;
      j++;
    }
  }
  return true
}

/*Returns true as it has 2 chars between aa and cc*/
alert(isExp("aaccbb", "aa2bb"))

/*Returns true as it has 2 chars between aa and cc and 4 chars between bb and cc*/
alert(isExp("aaccbbqqqqcc", "aa2bb4cc"))

/*Returns true as it has 10 chars between aa and cc */
alert(isExp("aaccbbqqqqsacc", "aa10cc"))

/*Returns false as the exp string as only 1 char between aa and bb */
alert(isExp("aacbb", "aa2bb"))
```
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Your first two test cases are returning false and your last two test cases are not returning anything! Also, I'm not super clear on what scenarios you are trying to test for. Could you elaborate your question? \$\endgroup\$
    – Rager
    Nov 22 '19 at 17:21
  • \$\begingroup\$ Hey Rager, Thanks for responding. The Question is you are given two strings expanded and compressed. Compressed string will have numbers in the string. Compressed string should have the same character left and right of the number. For Eg . Say expanded str = aabbcc and compressed str = aa2cc. These two strings should should result as true as there are 2 characters (bb) between aa and cc. Example2- if expStr = aabbbcc and compStr = aa2cc will return false as exp str has 3 characters between aa and cc. \$\endgroup\$
    – RamaM
    Nov 23 '19 at 17:01
2
\$\begingroup\$

Notice how close the syntax of your compressed strings resemble that of a regular expression:

   aa2bb => aa.{2}bb
aa2bb4cc => aa.{2}bb.{4}cc
  aa10cc => aa.{10}cc

Therefore you can easily create a regexp from your compressed string and test the expanded string against it:

function isExp(exp, comp) {
  const regexp = RegExp(`^${comp.replace(/\d+/g, '.{$&}')}$`)
  return regexp.test(exp);
}
\$\endgroup\$
3
  • \$\begingroup\$ Wow! Thats amazing. What will be the time/space complexity of this approach? \$\endgroup\$
    – RamaM
    Nov 23 '19 at 17:02
  • \$\begingroup\$ @RamaM I would think using regular expressions would be slower. Are you trying to get the fastest execution without caring much about readability? If so you should state that & maybe mention why (E.g part of a contest/challenge) \$\endgroup\$
    – dustytrash
    Nov 23 '19 at 18:04
  • \$\begingroup\$ Agreed. I want to know what is fastest and the best strategy to approach this problem. The solution i came up with is a linear solution O(n) with two pointer approach one for expanded string and one for compressed. \$\endgroup\$
    – RamaM
    Nov 23 '19 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.