-
Notifications
You must be signed in to change notification settings - Fork 30
Expand file tree
/
Copy pathone-edit.js
More file actions
103 lines (90 loc) · 2.27 KB
/
one-edit.js
File metadata and controls
103 lines (90 loc) · 2.27 KB
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/**
*
* @param {string} stringOne
* @param {string} stringTwo
* @returns {bool}
* Optimal Solution
* Time O(n) - Space O(1) - where n is the length of the shorter string
*/
function oneEdit(stringOne, stringTwo) {
const lengthOne = stringOne.length;
const lengthTwo = stringTwo.length;
if (Math.abs(lengthOne - lengthTwo) > 1) return false;
let madeEdit = false;
let indexOne = 0;
let indexTwo = 0;
while (indexOne < lengthOne && indexTwo < lengthTwo) {
if (stringOne[indexOne] !== stringTwo[indexTwo]) {
if (madeEdit) return false;
madeEdit = true;
if (lengthOne > lengthTwo) {
indexOne++;
} else if (lengthTwo > lengthOne) {
indexTwo++;
} else {
indexTwo++;
indexOne++;
}
} else {
indexOne++;
indexTwo++;
}
}
return true;
}
// Time O(n + m)
// Space O(n)
function oneEdit(stringOne, stringTwo) {
const lengthDiff = Math.abs(stringOne.length - stringTwo.length);
if (lengthDiff >= 2) return false;
let edit = 1;
if (lengthDiff === 1) {
const [str1, str2] = remove(stringOne, stringTwo);
if (str1 === str2) {
return true;
} else {
return false;
}
}
for (let i = 0; i < stringOne.length; i++) {
if (edit < 0) {
return false;
} else {
if (stringOne[i] === stringTwo[i]) continue;
edit--;
}
}
return true;
}
function remove(string1, string2) {
let largestString = string1.length > string2.length ? string1 : string2;
let smallestString = string1.length > string2.length ? string2 : string1;
let stringAfterRemoving = "";
const freq = {};
let letterToRemove = null;
for (const char of largestString) {
if (!freq.hasOwnProperty(char)) {
freq[char] = 1;
} else {
freq[char]++;
}
}
for (const char of smallestString) {
if (freq.hasOwnProperty(char)) {
freq[char]--;
if (freq[char] === 0) {
delete freq[char];
}
}
}
Object.keys(freq).forEach((key) => (letterToRemove = key));
let removeOne = 1;
for (let i = 0; i < largestString.length; i++) {
if (largestString[i] === letterToRemove && removeOne > 0) {
removeOne--;
continue;
}
stringAfterRemoving += largestString[i];
}
return [smallestString, stringAfterRemoving];
}