План курса / Все задачи / Алгоритмы и структуры данных

Поиск недостающего символа

легко

Даны две строки: s и t. Строка s представляет последовательность символов на кубиках, которые изначально находились на конвейере. Во время движения по конвейеру один кубик выпал, и строка t представляет символы оставшихся кубиков после этой потери.

Необходимо определить и вернуть символ, который был на выпавшем кубике.

Пример 1:

Ввод: s = "bcaeda", t = "aabcd"
Вывод: "e"

Пример 2:

Ввод: s = "e", t = ""
Вывод: "e"

Ограничения:

len(s) - 1 = len(t)
len(s) >= 1
Строки s и t содержат только буквы латинского алфавита

public class Solution {
    public static char FindMissingChar(String s, String t) {
        int result = 0;
        foreach (char ch in s) {
            result += (int)ch;
        }
        foreach (char ch in t) {
            result -= (int)ch;
        }
        return (char)result;
    }
}

#include <string>

using namespace std;

char findMissingChar(string s, string t) {
    int result = 0;
    for (char ch : s) {
        result += int(ch);
    }
    for (char ch : t) {
        result -= int(ch);
    }
    return char(result);
}

package main

func findMissingChar(s string, t string) rune {
    result := 0
    for _, ch := range s {
        result += int(ch)
    }
    for _, ch := range t {
        result -= int(ch)
    }
    return rune(result)
}

import java.util.*;

public class Solution {
    public Character findMissingChar(String s, String t) {
        int result = 0;
        for (char ch : s.toCharArray()) {
            result += (int) ch;
        }
        for (char ch : t.toCharArray()) {
            result -= (int) ch;
        }
        return (char) result;
    }
}

from typing import *

def find_missing_char(s: str, t: str) -> str:
    result = 0
    for ch in s:
        result += ord(ch)
    for ch in t:
        result -= ord(ch)
    return chr(result)

/**
* @param {string} s
* @param {string} t
* @returns {string}
*/
export function findMissingChar(s, t) {
    let result = 0;
    for (let ch of s) {
        result += ch.charCodeAt(0);
    }
    for (let ch of t) {
        result -= ch.charCodeAt(0);
    }
    return String.fromCharCode(result);
}

Оценка сложности

Время: O(n+m), где n - длина строки s, m - длина строки t
Память: O(1)

Так как len(s) - 1 = len(t), то оценка по времени как O(n) так же допустима.