План курса / Все задачи / Алгоритмы и структуры данных
Расстояние между X и Y
средне
# решено
Дана строка s, состоящая из алфавита "X", "Y", "O".
Необходимо найти и вернуть кратчайшее расстояние между буквами "X" и "Y", иначе 0.
Пример 1:
Ввод: s = "XX"
Вывод: 0
Пример 2:
Ввод: s = "XY"
Вывод: 1
Пример 3:
Ввод: s = "OOOXOOYOXO"
Вывод: 2
Ограничения:
len(s) >= 1
Строка s состоит только из заглавных букв 'X', 'Y' и 'O'.
public class Solution
{
public static int ShortestDistance(string s)
{
int prevXIdx = -1; // Позиция последнего встреченного X
int prevYIdx = -1; // Позиция последнего встреченного Y
int result = s.Length + 1;
for (int idx = 0; idx < s.Length; idx++)
{
if (s[idx] == 'X')
{
if (prevYIdx != -1)
{
result = Math.Min(result, idx - prevYIdx);
}
prevXIdx = idx;
}
if (s[idx] == 'Y')
{
if (prevXIdx != -1)
{
result = Math.Min(result, idx - prevXIdx);
}
prevYIdx = idx;
}
}
if (result == s.Length + 1)
{
return 0;
}
return result;
}
}
#include <string>
#include <algorithm>
using namespace std;
int shortestDistance(string s) {
int prevXIdx = -1; // позиция последнего встреченного X
int prevYIdx = -1; // позиция последнего встреченного Y
int result = s.size() + 1;
for (int idx = 0; idx < s.size(); idx++) {
if (s[idx] == 'X') {
if (prevYIdx != -1) {
result = min(result, idx - prevYIdx);
}
prevXIdx = idx;
}
if (s[idx] == 'Y') {
if (prevXIdx != -1) {
result = min(result, idx - prevXIdx);
}
prevYIdx = idx;
}
}
if (result == (int)s.size() + 1) {
return 0;
}
return result;
}
package main
func shortestDistance(s string) int {
prevXIdx := -1 // позиция последнего встреченного X
prevYIdx := -1 // позиция последнего встреченного Y
result := len(s) + 1
for idx, val := range s {
if val == 'X' {
if prevYIdx != -1 && idx-prevYIdx < result {
result = idx - prevYIdx
}
prevXIdx = idx
}
if val == 'Y' {
if prevXIdx != -1 && idx-prevXIdx < result {
result = idx - prevXIdx
}
prevYIdx = idx
}
}
if result == len(s)+1 {
return 0
}
return result
}
import java.util.*;
public class Solution {
public static int shortestDistance(String s) {
int prevXIdx = -1; // позиция последнего встреченного X
int prevYIdx = -1; // позиция последнего встреченного Y
int result = s.length() + 1;
for (int idx = 0; idx < s.length(); idx++) {
if (s.charAt(idx) == 'X') {
if (prevYIdx != -1) {
result = Math.min(result, idx - prevYIdx);
}
prevXIdx = idx;
}
if (s.charAt(idx) == 'Y') {
if (prevXIdx != -1) {
result = Math.min(result, idx - prevXIdx);
}
prevYIdx = idx;
}
}
if (result == s.length() + 1) {
return 0;
}
return result;
}
}
import java.util.*;
public class Solution {
public static int shortestDistance(String s) {
int prevXIdx = -1; // позиция последнего встреченного X
int prevYIdx = -1; // позиция последнего встреченного Y
int result = s.length() + 1;
for (int idx = 0; idx < s.length(); idx++) {
if (s.charAt(idx) == 'X') {
if (prevYIdx != -1) {
result = Math.min(result, idx - prevYIdx);
}
prevXIdx = idx;
}
if (s.charAt(idx) == 'Y') {
if (prevXIdx != -1) {
result = Math.min(result, idx - prevXIdx);
}
prevYIdx = idx;
}
}
if (result == s.length() + 1) {
return 0;
}
return result;
}
}
from typing import *
def shortest_distance(s: str) -> int:
prev_x_idx = None # позиция последнего встреченного X
prev_y_idx = None # позиция последнего встреченного Y
result = len(s) + 1
for idx, val in enumerate(s):
if val == "X":
if prev_y_idx is not None:
result = min(result, idx - prev_y_idx)
prev_x_idx = idx
if val == "Y":
if prev_x_idx is not None:
result = min(result, idx - prev_x_idx)
prev_y_idx = idx
if result == len(s) + 1:
return 0
return result