389. Find the Difference

leetcode easy

#array#csharp#easy#leetcode#search#sort#string

Task

Даны две строки s и t.

Строка t генерируется путем случайного перемешивания строки s с добавлением еще одной буквы в случайную позицию.

Верните букву, которая была добавлена в t.

Пример:

Input: s = "abcd", t = "abcde"

Output: "e"

Explanation: 'e' is the letter that was added.

C# solution

matched/original

using System;
public class Solution {
    public char FindTheDifference(string s, string t) {
        char[] sortedS = s.ToCharArray();
        char[] sortedT = t.ToCharArray();
        Array.Sort(sortedS);
        Array.Sort(sortedT);
        int i = 0;
        while (i < s.Length) {
            if (sortedS[i] != sortedT[i]) {
                return sortedT[i];
            }
            i += 1;
        }
        return sortedT[i];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public char FindTheDifference(string s, string t) {
        char[] sortedS = s.ToCharArray();
        char[] sortedT = t.ToCharArray();
        sort(sortedS.begin(), sortedS.end());
        sort(sortedT.begin(), sortedT.end());
        int i = 0;
        while (i < s.size()) {
            if (sortedS[i] != sortedT[i]) {
                return sortedT[i];
            }
            i += 1;
        }
        return sortedT[i];
    }
}

Java solution

matched/original

class Solution {
    public char findTheDifference(String s, String t) {
        char[] sortedS = s.toCharArray();
        char[] sortedT = t.toCharArray();
        Arrays.sort(sortedS);
        Arrays.sort(sortedT);

        int i = 0;
        while (i < s.length()) {
            if (sortedS[i] != sortedT[i]) {
                return sortedT[i];
            }
            i += 1;
        }

        return sortedT[i];
    }
}

JavaScript solution

matched/original

var findTheDifference = function(s, t) {
    let sortedS = s.split('').sort();
    let sortedT = t.split('').sort();

    for (let i = 0; i < sortedS.length; i++) {
        if (sortedS[i] !== sortedT[i]) {
            return sortedT[i];
        }
    }

    return sortedT[sortedS.length];
};

Python solution

matched/original

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        sorted_s = sorted(s)
        sorted_t = sorted(t)

        for i in range(len(sorted_s)):
            if sorted_s[i] != sorted_t[i]:
                return sorted_t[i]

        return sorted_t[len(sorted_s)]

Go solution

matched/original

package main

import (
    "sort"
    "strings"
)

func findTheDifference(s string, t string) byte {
    sortedS := strings.Split(s, "")
    sortedT := strings.Split(t, "")
    sort.Strings(sortedS)
    sort.Strings(sortedT)

    for i := 0; i < len(sortedS); i++ {
        if sortedS[i] != sortedT[i] {
            return sortedT[i][0]
        }
    }

    return sortedT[len(sortedS)][0]
}

Explanation

Algorithm

Отсортируйте строки s и t.

Итерируйте по длине строк и сравнивайте их посимвольно. Это позволяет проверить, присутствует ли текущий символ строки t в строке s.

Как только встретится символ, который есть в строке t, но отсутствует в строке s, мы найдем лишний символ, который скрывала строка t все это время.

😎