LeetCode Solutions (161 серия деталей)
Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашли его полезным, Пожалуйста, нравится Этот пост и/или upvote Мое решение по сообщению на форумах LeetCode Анкет
Проблема LeetCode #336 (жестко): Палиндром пары
Описание:
( прыгнуть в : Идея решения Код : JavaScript | Python | Java | C ++
Дал список уникальный слова , вернуть все пары различный Индексы ( i, j ) в данном списке, так что объединение двух слов слова [i] + слова [j] это палиндром.
Примеры:
| Вход: | слова = [“abcd”, “dcba”, “lls”, “s”, “sssll”] |
| Выход: | [[0,1],[1,0],[3,2],[2,4]] |
| Объяснение: | Палиндромы – это [“dcbaabcd”, “abcddcba”, “slls”, “llssssll”] |
| Вход: | слова = [“Bat”, “Tab”, “Cat”] |
| Выход: | [[0,1],[1,0]] |
| Объяснение: | Палиндромы [“Battab”, “tabbat”] |
| Вход: | слова = [“a”,””] |
| Выход: | [[0,1],[1,0]] |
Ограничения:
1. длиной0 [i] .lengthслова [i]состоит из более низких английских букв.
Идея:
( Прыгните к : Описание задачи Код : JavaScript | Python | Java | C ++
Наивный подход здесь предпримет любое возможное сочетание слова , но это было бы неэффективно. Вместо этого мы можем выяснить, какие возможные слова будут сочетаться с каждым словом, и, в частности, проверить их.
Для этого нам сначала придется хранить каждое слово в карта Структура ( wmap ), со словом как ключ и индекс как значение. Таким образом, мы можем найти любые возможные совпадения с текущим словом, когда мы перечислим через слова Анкет
Следующее, что мы захотим сделать, это определить вспомогательную функцию ( ispal ), чтобы проверить, является ли слово палиндром. Вместо того, чтобы передать ему подстроение слова, мы можем определить его, чтобы принять ряд индексов для проверки, чтобы мы не постоянно строим новые строки.
Как мы переживаем через слова , тогда каждое слово, возможно, будет соответствовать другому слову одним из трех способов:
- Пустое струнное слово будет совпадать с любой стороны с любым словом палиндрома. (например, “” будет совпадать с “ABC” и наоборот)
- Полное слово будет совпадать с обеих сторон с его обратной версией. (например, «ABC» будет соответствовать «CBA», и наоборот)
- Частичное слово будет соответствовать его обратной версии на противоположной стороне, если оставшаяся часть слова является палиндром (например, «Abcddd» будет соответствовать «CBA», потому что «ABC» соответствует «CBA», а «DDD» – палиндром)
Первая проверка легко выполнить. Если мы найдем пустую строку, мы сможем перевернуть все слова Перечислите дополнительное время поиска палиндромов, чтобы соответствовать. Нам просто нужно помнить, чтобы не соответствовать пустой строке с собой.
Для второй проверки, так как мы в конечном итоге выехали на соответствующее полное слово, мы должны добавить одну пару в настоящее время, а не оба, так как мы сможем добавить второй заказ той же пары, когда мы получим ко второму слову.
Третья проверка самая сложная. Для этого мы захотим сначала изменить текущее слово в его обратную версию ( bw ), так как мы будем сопоставить существующие фронтальные слова в wmap Анкет Тогда мы должны повторить индексы самого слова, проверяя обе стороны делящего индекса ( j ), чтобы быть палиндром.
Если найден палиндром, то мы можем попытаться найти Другое часть слова в wmap Анкет Если совпадение найдено, мы можем подтолкнуть эту пару к нашему массиву ответов ( ans ). В конце итерации слова , мы можем вернуть ANS Анкет
- Сложность времени: O (n * m^2) куда N является длиной слова а также M Средняя длина слов в слова
- Сложность пространства: O (n) за Wmap
Код JavaScript:
( Прыгните к : Описание задачи Идея решения
var palindromePairs = function(words) {
let wmap = new Map(), ans = []
for (let i = 0; i < words.length; i++)
wmap.set(words[i], i)
for (let i = 0; i < words.length; i++) {
if (words[i] === "") {
for (let j = 0; j < words.length; j++)
if (isPal(words[j]) && j !== i)
ans.push([i, j], [j, i])
continue
}
let bw = words[i].split("").reverse().join("")
let res = wmap.get(bw)
if (res !== undefined && res !== i)
ans.push([i, res])
for (let j = 1; j < bw.length; j++) {
if (isPal(bw, 0, j - 1)) {
let res = wmap.get(bw.slice(j))
if (res !== undefined)
ans.push([i, res])
}
if (isPal(bw, j)) {
let res = wmap.get(bw.slice(0,j))
if (res !== undefined)
ans.push([res, i])
}
}
}
return ans
};
const isPal = (word, i=0, j=word.length-1) => {
while (i < j)
if (word[i++] !== word[j--]) return false
return true
}
Код Python:
( Прыгните к : Описание задачи Идея решения
class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
wmap, ans = {}, []
for i in range(len(words)):
wmap[words[i]] = i
for i in range(len(words)):
if words[i] == "":
for j in range(len(words)):
w = words[j]
if self.isPal(w, 0, len(w)-1) and j != i:
ans.append([i, j])
ans.append([j, i])
continue
bw = words[i][::-1]
if bw in wmap:
res = wmap[bw]
if res != i: ans.append([i, res])
for j in range(1, len(bw)):
if self.isPal(bw, 0, j - 1) and bw[j:] in wmap:
ans.append([i, wmap[bw[j:]]])
if self.isPal(bw, j, len(bw)-1) and bw[:j] in wmap:
ans.append([wmap[bw[:j]], i])
return ans
def isPal(self, word: str, i: int, j: int) -> bool:
while i < j:
if word[i] != word[j]: return False
i += 1
j -= 1
return True
Код Java:
( Прыгните к : Описание задачи Идея решения
class Solution {
public List> palindromePairs(String[] words) {
Map wmap = new HashMap<>();
List> ans = new ArrayList<>();
for (int i = 0; i < words.length; i++)
wmap.put(words[i], i);
for (int i = 0; i < words.length; i++) {
if (words[i].equals("")) {
for (int j = 0; j < words.length; j++) {
String w = words[j];
if (isPal(w, 0, w.length()-1) && j != i) {
ans.add(List.of(i, j));
ans.add(List.of(j, i));
}
}
continue;
}
StringBuilder sb = new StringBuilder(words[i]);
sb.reverse();
String bw = sb.toString();
if (wmap.containsKey(bw)) {
int res = wmap.get(bw);
if (res != i) ans.add(List.of(i, res));
}
for (int j = 1; j < bw.length(); j++) {
if (isPal(bw, 0, j-1)) {
String s = bw.substring(j);
if (wmap.containsKey(s))
ans.add(List.of(i, wmap.get(s)));
}
if (isPal(bw, j, bw.length()-1)) {
String s = bw.substring(0,j);
if (wmap.containsKey(s))
ans.add(List.of(wmap.get(s), i));
}
}
}
return ans;
}
private boolean isPal(String word, int i, int j) {
while (i < j)
if (word.charAt(i++) != word.charAt(j--)) return false;
return true;
}
}
C ++ Код:
( Прыгните к : Описание задачи Идея решения
class Solution {
public:
vector> palindromePairs(vector& words) {
unordered_map wmap;
vector> ans;
for (int i = 0; i < words.size(); i++)
wmap[words[i]] = i;
for (int i = 0; i < words.size(); i++) {
if (words[i] == "") {
for (int j = 0; j < words.size(); j++) {
string& w = words[j];
if (isPal(w, 0, w.size()-1) && j != i) {
ans.push_back(vector {i, j});
ans.push_back(vector {j, i});
}
}
continue;
}
string bw = words[i];
reverse(bw.begin(), bw.end());
if (wmap.find(bw) != wmap.end()) {
int res = wmap[bw];
if (res != i) ans.push_back(vector {i, res});
}
for (int j = 1; j < bw.size(); j++) {
if (isPal(bw, 0, j-1)) {
string s = bw.substr(j, bw.size()-j);
if (wmap.find(s) != wmap.end())
ans.push_back(vector {i, wmap[s]});
}
if (isPal(bw, j, bw.size()-1)) {
string s = bw.substr(0, j);
if (wmap.find(s) != wmap.end())
ans.push_back(vector {wmap[s], i});
}
}
}
return ans;
}
private:
bool isPal(string& word, int i, int j) {
while (i < j)
if (word[i++] != word[j--]) return false;
return true;
}
};
LeetCode Solutions (161 серия деталей)
Оригинал: “https://dev.to/seanpgallivan/solution-palindrome-pairs-23j6”