ค้นหาความแตกต่าง Leetcode Solution


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อะโดบี อเมซอน Google
hashing เชือก

ในปัญหานี้เราได้รับสอง เงื่อนไข. สตริงที่สองสร้างขึ้นโดยการสับอักขระของสตริงแรกแบบสุ่มจากนั้นเพิ่มอักขระพิเศษที่ตำแหน่งสุ่มใด ๆ เราจำเป็นต้องส่งคืนอักขระพิเศษที่ถูกเพิ่มเข้าไปในสตริงที่สอง อักขระจะเป็นตัวอักษรภาษาอังกฤษตัวพิมพ์เล็กเสมอ

ตัวอย่าง

a = "abcde" , b = "ebacdf"
f
a = "aaaa" , b = "aaaaa"
a

คำอธิบาย # 1

อักขระพิเศษที่ถูกเพิ่มลงในสตริง b คือ 'f' เป็นสตริง a ไม่มีมัน

คำอธิบาย # 2

เชือก มีตัวอักษร "a" 4 ตัวในขณะที่สตริง มี 5 ดังนั้นตัวอักษรพิเศษคือ 'a'

วิธีการ (การเรียงลำดับ)

เราสามารถเรียงลำดับสตริงทั้งสองแล้ววนซ้ำทั้งสองตัวอักษรทีละตัวอักษรเพื่อค้นหาตำแหน่งแรกที่แตกต่างกัน สตริงที่สองจะมีหนึ่งเสมอ พิเศษ ตัวละคร. ดังนั้นเราจะพบจุดที่สตริงเสมอ a และ b แตกต่างกัน อย่างไรก็ตามอาจมีกรณีที่สตริง b หลังจากการเรียงลำดับตรงกับอักขระทุกตัวในสตริง a ใน แต่มีอักขระพิเศษหนึ่งตัวในตอนท้าย เราจำเป็นต้องจัดการเรื่องนี้เป็นกรณีพิเศษ

ค้นหาความแตกต่าง Leetcode Solution

ขั้นตอนวิธี

  1. เรียงลำดับทั้งสองสตริง a และ b. เนื่องจากเป็นไปไม่ได้ใน java ก่อนอื่นเราจึงแปลงเป็นไฟล์ อาร์เรย์ถ่าน
  2. สำหรับทุกอักขระที่มีอยู่ในสตริงที่สั้นกว่าเราจะตรวจสอบตัวอักษรทีละตัว:
    • ถ้าอักขระในสตริง ไม่เท่ากับอักขระที่เกี่ยวข้องในสตริง b:
      • ส่งคืนอักขระนี้
  3. ส่งกลับอักขระสุดท้ายของสตริง เนื่องจากเป็นตัวละครพิเศษ
  4. พิมพ์ผลลัพธ์

การดำเนินการค้นหาความแตกต่าง Leetcode Solution

โปรแกรม C ++

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

char findTheDifference(string a , string b)
{
    sort(a.begin() , a.end());
    sort(b.begin() , b.end());
    int n = a.size();
    for(int i = 0 ; i < n ; i++)
        if(a[i] != b[i])
            return b[i];
    return b[n];
}

int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

โปรแกรม Java

import java.util.Arrays;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        char[] a_CharArray = a.toCharArray();
        char[] b_charArray = b.toCharArray();

        Arrays.sort(a_CharArray);
        Arrays.sort(b_charArray);

        int n = a.length();
        for(int i = 0 ; i < n ; i++)
            if(a_CharArray[i] != b_charArray[i])
                return b_charArray[i];
        return b_charArray[n];
    }
}
f

การวิเคราะห์ความซับซ้อนของการค้นหาความแตกต่าง Leetcode Solution

ความซับซ้อนของเวลา

O (NlogN)โดยที่ N = ความยาวของสตริงที่ยาวกว่า เราเรียงลำดับสตริง / อาร์เรย์ถ่านซึ่งใช้เวลา O (NlogN)

ความซับซ้อนของพื้นที่

บน) ใน java และ O (1) ใน C ++ เมื่อเราแปลงสตริงเป็นไฟล์ ถ่านอาร์เรย์ ใน java

วิธีการ (Hashing)

ในทั้งสองสตริงเราสามารถแฮชอักขระทุกตัวด้วยความถี่และค้นหาอักขระที่แตกต่างกันในความถี่ เนื่องจากเรามีอักขระที่ไม่ซ้ำกันจำนวนคงที่ อัลกอริทึมนี้เร็วกว่าที่กล่าวไว้ข้างต้น ในการใช้งานที่มีประสิทธิภาพเราสามารถสร้างไฟล์ ตารางแฮช และเพิ่มความถี่สำหรับทุกอักขระในสตริง a และลดความถี่สำหรับทุกอักขระในสตริง b. สิ่งนี้จะทำให้เราอยู่ในกรณีที่ความถี่ของอักขระหนึ่งตัวคือ ไม่ใช่ศูนย์ และนี่จะเป็นอักขระพิเศษในสตริง b.

ขั้นตอนวิธี

  1. เริ่มต้นตารางแฮชเพื่อจัดเก็บความถี่ของอักขระทั้งหมดเป็น ความถี่
  2. สำหรับทุกอักขระในสตริง a:
    • เพิ่มความถี่ในตารางแฮช
  3. สำหรับทุกอักขระในสตริง b:
    • ลดความถี่ในตารางแฮช
    • ถ้าความถี่เท่ากับ -1:
      • ส่งคืนอักขระนี้
  4. Return '-' เพื่อรักษาไวยากรณ์ของฟังก์ชัน
  5. พิมพ์ผลลัพธ์

การดำเนินการค้นหาความแตกต่าง Leetcode Solution

โปรแกรม C ++

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

char findTheDifference(string a , string b)
{
    unordered_map <int , int> frequency;
    for(char &c : a)
        frequency[c]++;
    for(char &c : b)
    {
        frequency[c]--;
        if(frequency[c] == -1)
            return c;
    }
    //this case will never happen
    return '-';
}


int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

โปรแกรม Java

import java.util.*;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        HashMap <Character , Integer> frequency = new HashMap<>();
        char x;
        for(int i = 0 ; i < a.length() ; i++)
        {
            x = a.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) + 1);
        }

        for(int i = 0 ; i < b.length() ; i++)
        {
            x = b.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) - 1);
            if(frequency.getOrDefault(x , 0) == -1)
                return x;
        }
        //this case will never occur
        return '-';
    }
}
f

การวิเคราะห์ความซับซ้อนของการค้นหาความแตกต่าง Leetcode Solution

ความซับซ้อนของเวลา

บน), N = ขนาดของสตริงที่ยาวขึ้น, ในขณะที่เราสำรวจทั้งสองสตริงหนึ่งครั้งเพื่ออัปเดตความถี่ของอักขระ

ความซับซ้อนของพื้นที่

O (1). แม้ว่าเราจะใช้แฮชแท็กในการจัดเก็บอักขระด้วยความถี่ แต่เราใช้พื้นที่คงที่โดยไม่คำนึงถึงอินพุต ดังนั้นความซับซ้อนของพื้นที่จึงคงที่