|
| 1 | +/** |
| 2 | + *@description |
| 3 | + * Given two strings, `source` and `target`, determine if it's possible to make `source` equal |
| 4 | + * to `target` You can perform the following operations on the string `source`: |
| 5 | + * 1. Capitalize zero or more of `source`'s lowercase letters. |
| 6 | + * 2. Delete all the remaining lowercase letters in `source`. |
| 7 | + * |
| 8 | + * Time Complexity: (O(|source|*|target|)) where `|source|` => length of string `source` |
| 9 | + * |
| 10 | + *@param {String} source - The string to be transformed. |
| 11 | + *@param {String} target - The string we want to transform `source` into. |
| 12 | + *@returns {Boolean} - Whether the transformation is possible. |
| 13 | + *@see https://www.hackerrank.com/challenges/abbr/problem - Related problem on HackerRank. |
| 14 | + */ |
| 15 | +exportconstisAbbreviation=(source,target)=>{ |
| 16 | +constsourceLength=source.length |
| 17 | +consttargetLength=target.length |
| 18 | + |
| 19 | +// Initialize a table to keep track of possible abbreviations |
| 20 | +letcanAbbreviate=Array.from({length:sourceLength+1},()=> |
| 21 | +Array(targetLength+1).fill(false) |
| 22 | +) |
| 23 | +// Empty strings are trivially abbreviatable |
| 24 | +canAbbreviate[0][0]=true |
| 25 | + |
| 26 | +for(letsourceIndex=0;sourceIndex<sourceLength;sourceIndex++){ |
| 27 | +for(lettargetIndex=0;targetIndex<=targetLength;targetIndex++){ |
| 28 | +if(canAbbreviate[sourceIndex][targetIndex]){ |
| 29 | +// If characters at the current position are equal, move to the next position in both strings. |
| 30 | +if( |
| 31 | +targetIndex<targetLength&& |
| 32 | +source[sourceIndex].toUpperCase()===target[targetIndex] |
| 33 | +){ |
| 34 | +canAbbreviate[sourceIndex+1][targetIndex+1]=true |
| 35 | +} |
| 36 | +// If the current character in `source` is lowercase, explore two possibilities: |
| 37 | +// a) Capitalize it (which is akin to "using" it in `source` to match `target`), or |
| 38 | +// b) Skip it (effectively deleting it from `source`). |
| 39 | +if(source[sourceIndex]===source[sourceIndex].toLowerCase()){ |
| 40 | +canAbbreviate[sourceIndex+1][targetIndex]=true |
| 41 | +} |
| 42 | +} |
| 43 | +} |
| 44 | +} |
| 45 | + |
| 46 | +returncanAbbreviate[sourceLength][targetLength] |
| 47 | +} |