FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
JavaScript/Dynamic-Programming/Abbreviation.js at master · TheAlgorithms/JavaScript · GitHub
Uh oh!
There was an error while loading.
Please reload this page
.
TheAlgorithms
/
JavaScript
Public
Uh oh!
There was an error while loading.
Please reload this page
.
Notifications
You must be signed in to change notification settings
Fork
5.8k
Star
34.2k
Code
Issues
21
Pull requests
192
Actions
Projects
Wiki
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
JavaScript
/
Dynamic-Programming
/
Abbreviation.js
Copy path
More file actions
More file actions
Latest commit
History
History
History
47 lines (44 loc) · 2.01 KB
Breadcrumbs
JavaScript
/
Dynamic-Programming
/
Abbreviation.js
Copy path
File metadata and controls
47 lines (44 loc) · 2.01 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
*
@description
* Given two strings, `source` and `target`, determine if it's possible to make `source` equal
* to `target` You can perform the following operations on the string `source`:
* 1. Capitalize zero or more of `source`'s lowercase letters.
* 2. Delete all the remaining lowercase letters in `source`.
*
* Time Complexity: (O(|source|*|target|)) where `|source|` => length of string `source`
*
*
@param
{
String
} source - The string to be transformed.
*
@param
{
String
} target - The string we want to transform `source` into.
*
@returns
{
Boolean
} - Whether the transformation is possible.
*
@see
https://www.hackerrank.com/challenges/abbr/problem - Related problem on HackerRank.
*/
export
const
isAbbreviation
=
(
source
,
target
)
=>
{
const
sourceLength
=
source
.
length
const
targetLength
=
target
.
length
// Initialize a table to keep track of possible abbreviations
let
canAbbreviate
=
Array
.
from
(
{
length
:
sourceLength
+
1
}
,
(
)
=>
Array
(
targetLength
+
1
)
.
fill
(
false
)
)
// Empty strings are trivially abbreviatable
canAbbreviate
[
0
]
[
0
]
=
true
for
(
let
sourceIndex
=
0
;
sourceIndex
<
sourceLength
;
sourceIndex
++
)
{
for
(
let
targetIndex
=
0
;
targetIndex
<=
targetLength
;
targetIndex
++
)
{
if
(
canAbbreviate
[
sourceIndex
]
[
targetIndex
]
)
{
// If characters at the current position are equal, move to the next position in both strings.
if
(
targetIndex
<
targetLength
&&
source
[
sourceIndex
]
.
toUpperCase
(
)
===
target
[
targetIndex
]
)
{
canAbbreviate
[
sourceIndex
+
1
]
[
targetIndex
+
1
]
=
true
}
// If the current character in `source` is lowercase, explore two possibilities:
// a) Capitalize it (which is akin to "using" it in `source` to match `target`), or
// b) Skip it (effectively deleting it from `source`).
if
(
source
[
sourceIndex
]
===
source
[
sourceIndex
]
.
toLowerCase
(
)
)
{
canAbbreviate
[
sourceIndex
+
1
]
[
targetIndex
]
=
true
}
}
}
}
return
canAbbreviate
[
sourceLength
]
[
targetLength
]
}
Back
|
FazBrowse Home
|
New Git URL