ವ್ಯತ್ಯಾಸ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಹುಡುಕಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಗೂಗಲ್
ಹ್ಯಾಶಿಂಗ್ ಸ್ಟ್ರಿಂಗ್

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ಎರಡು ನೀಡಲಾಗುತ್ತದೆ ತಂತಿಗಳು. ಮೊದಲ ಸ್ಟ್ರಿಂಗ್‌ನ ಅಕ್ಷರಗಳನ್ನು ಯಾದೃಚ್ ly ಿಕವಾಗಿ ಬದಲಾಯಿಸುವ ಮೂಲಕ ಮತ್ತು ನಂತರ ಯಾವುದೇ ಯಾದೃಚ್ position ಿಕ ಸ್ಥಾನದಲ್ಲಿ ಹೆಚ್ಚುವರಿ ಅಕ್ಷರವನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಎರಡನೇ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ರಚಿಸಲಾಗುತ್ತದೆ. ಎರಡನೇ ಸ್ಟ್ರಿಂಗ್‌ಗೆ ಸೇರಿಸಲಾದ ಹೆಚ್ಚುವರಿ ಅಕ್ಷರವನ್ನು ನಾವು ಹಿಂತಿರುಗಿಸಬೇಕಾಗಿದೆ. ಅಕ್ಷರಗಳು ಯಾವಾಗಲೂ ಲೋವರ್-ಕೇಸ್ ಇಂಗ್ಲಿಷ್ ಅಕ್ಷರಗಳಾಗಿರುತ್ತವೆ.

ಉದಾಹರಣೆ

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

ವಿವರಣೆ # 1

ಸ್ಟ್ರಿಂಗ್‌ಗೆ ಸೇರಿಸಲಾದ ಹೆಚ್ಚುವರಿ ಅಕ್ಷರ b ಸ್ಟ್ರಿಂಗ್‌ನಂತೆ 'f' ಆಗಿದೆ a ಅದನ್ನು ಒಳಗೊಂಡಿಲ್ಲ.

ವಿವರಣೆ # 2

ಸ್ಟ್ರಿಂಗ್ ಸ್ಟ್ರಿಂಗ್ ಮಾಡುವಾಗ 4 'ಎ' ಅಕ್ಷರಗಳನ್ನು ಹೊಂದಿದೆ ಹೊಂದಿದೆ 5. ಆದ್ದರಿಂದ, ಹೆಚ್ಚುವರಿ ಅಕ್ಷರ 'ಎ' ಆಗಿದೆ.

ಅಪ್ರೋಚ್ (ವಿಂಗಡಣೆ)

ನಾವು ಎರಡೂ ತಂತಿಗಳನ್ನು ವಿಂಗಡಿಸಬಹುದು ಮತ್ತು ನಂತರ ಅವುಗಳು ಭಿನ್ನವಾಗಿರುವ ಮೊದಲ ಸ್ಥಾನವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಅಕ್ಷರಗಳ ಮೂಲಕ ಅಕ್ಷರಗಳ ಮೂಲಕ ಪುನರಾವರ್ತಿಸಬಹುದು. ಎರಡನೇ ಸ್ಟ್ರಿಂಗ್ ಯಾವಾಗಲೂ ಒಂದನ್ನು ಹೊಂದಿರುತ್ತದೆ ಹೆಚ್ಚುವರಿ ಪಾತ್ರ. ಆದ್ದರಿಂದ, ನಾವು ಯಾವಾಗಲೂ ಸ್ಟ್ರಿಂಗ್ ಇರುವ ಸ್ಥಳವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತೇವೆ a ಮತ್ತು b ಭಿನ್ನವಾಗಿರುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಸ್ಟ್ರಿಂಗ್ ಇರುವ ಸಂದರ್ಭವಿರಬಹುದು b ವಿಂಗಡಿಸಿದ ನಂತರ ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಅಕ್ಷರಕ್ಕೂ ಹೊಂದಿಕೆಯಾಗುತ್ತದೆ a ರಲ್ಲಿ ಆದರೆ ಕೊನೆಯಲ್ಲಿ ಒಂದು ಹೆಚ್ಚುವರಿ ಅಕ್ಷರವನ್ನು ಹೊಂದಿದೆ. ಈ ಒಂದು ವಿಶೇಷ ಪ್ರಕರಣವನ್ನು ನಾವು ನಿರ್ವಹಿಸಬೇಕಾಗಿದೆ.

ವ್ಯತ್ಯಾಸ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಹುಡುಕಿ

ಕ್ರಮಾವಳಿ

  1. ಎರಡೂ ತಂತಿಗಳನ್ನು ವಿಂಗಡಿಸಿ, a ಮತ್ತು b. ಜಾವಾದಲ್ಲಿ ಅದು ಸಾಧ್ಯವಾಗದ ಕಾರಣ, ನಾವು ಮೊದಲು ಅವುಗಳನ್ನು ಪರಿವರ್ತಿಸುತ್ತೇವೆ ಚಾರ್ ಅರೇಗಳು
  2. ಚಿಕ್ಕದಾದ ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಅಕ್ಷರಕ್ಕೂ, ನಾವು ಅಕ್ಷರದ ಮೂಲಕ ಅಕ್ಷರದ ಪರಿಶೀಲನೆ ಮಾಡುತ್ತೇವೆ:
    • ಅಕ್ಷರ ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿದ್ದರೆ ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿನ ಅನುಗುಣವಾದ ಅಕ್ಷರಕ್ಕೆ ಸಮನಾಗಿರುವುದಿಲ್ಲ b:
      • ಈ ಅಕ್ಷರವನ್ನು ಹಿಂತಿರುಗಿ.
  3. ಸ್ಟ್ರಿಂಗ್‌ನ ಕೊನೆಯ ಅಕ್ಷರವನ್ನು ಹಿಂತಿರುಗಿ ಇದು ಹೆಚ್ಚುವರಿ ಪಾತ್ರವಾಗಿರುವುದರಿಂದ
  4. ಫಲಿತಾಂಶವನ್ನು ಮುದ್ರಿಸಿ

ಫೈಂಡ್ ದಿ ಡಿಫರೆನ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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;
}

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

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

ವ್ಯತ್ಯಾಸವನ್ನು ಕಂಡುಕೊಳ್ಳುವ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್‌ಲಾಗ್ಎನ್), ಅಲ್ಲಿ N = ಉದ್ದದ ಸ್ಟ್ರಿಂಗ್‌ನ ಉದ್ದ. O (NlogN) ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುವ ತಂತಿಗಳು / ಚಾರ್ ಸರಣಿಗಳನ್ನು ನಾವು ವಿಂಗಡಿಸುತ್ತೇವೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್) ಜಾವಾ ಮತ್ತು ಒ (1) ಸಿ ++ ನಲ್ಲಿ ನಾವು ತಂತಿಗಳನ್ನು ಪರಿವರ್ತಿಸುತ್ತೇವೆ ಚಾರ್ ಅರೇಸ್ ಜಾವಾದಲ್ಲಿ.

ಅಪ್ರೋಚ್ (ಹ್ಯಾಶಿಂಗ್)

ಎರಡೂ ತಂತಿಗಳಲ್ಲಿ, ನಾವು ಪ್ರತಿ ಅಕ್ಷರವನ್ನು ಅದರ ಆವರ್ತನದೊಂದಿಗೆ ಹ್ಯಾಶ್ ಮಾಡಬಹುದು ಮತ್ತು ಆವರ್ತನದಲ್ಲಿ ಭಿನ್ನವಾಗಿರುವ ಅಕ್ಷರವನ್ನು ಕಂಡುಹಿಡಿಯಬಹುದು. ನಾವು ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಅನನ್ಯ ಅಕ್ಷರಗಳನ್ನು ಹೊಂದಿರುವುದರಿಂದ. ಈ ಅಲ್ಗಾರಿದಮ್ ಮೇಲೆ ಚರ್ಚಿಸಿದ ವಿಧಾನಕ್ಕಿಂತ ವೇಗವಾಗಿರುತ್ತದೆ. ದಕ್ಷ ಅನುಷ್ಠಾನವಾಗಿ, ನಾವು ಎ ಹ್ಯಾಶ್ ಟೇಬಲ್ ಮತ್ತು ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಅಕ್ಷರಕ್ಕೂ ಆವರ್ತನವನ್ನು ಹೆಚ್ಚಿಸಿ a ಮತ್ತು ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಅಕ್ಷರಕ್ಕೂ ಆವರ್ತನವನ್ನು ಕಡಿಮೆ ಮಾಡಿ b. ನಿಖರವಾಗಿ ಒಂದು ಪಾತ್ರದ ಆವರ್ತನ ಇರುವ ಸಂದರ್ಭದಲ್ಲಿ ಇದು ನಮ್ಮನ್ನು ಬಿಡುತ್ತದೆ ಶೂನ್ಯೇತರ ಮತ್ತು ಇದು ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿರುವ ಹೆಚ್ಚುವರಿ ಅಕ್ಷರವಾಗಿರುತ್ತದೆ b.

ಕ್ರಮಾವಳಿ

  1. ಎಲ್ಲಾ ಅಕ್ಷರಗಳ ಆವರ್ತನವನ್ನು ಸಂಗ್ರಹಿಸಲು ಹ್ಯಾಶ್ ಟೇಬಲ್ ಅನ್ನು ಪ್ರಾರಂಭಿಸಿ ಆವರ್ತನ
  2. ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಪಾತ್ರಕ್ಕೂ a:
    • ಹ್ಯಾಶ್ ಕೋಷ್ಟಕದಲ್ಲಿ ಅದರ ಆವರ್ತನವನ್ನು ಹೆಚ್ಚಿಸಿ
  3. ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಪಾತ್ರಕ್ಕೂ b:
    • ಹ್ಯಾಶ್ ಕೋಷ್ಟಕದಲ್ಲಿ ಅದರ ಆವರ್ತನವನ್ನು ಕಡಿಮೆ ಮಾಡಿ
    • ಅದರ ಆವರ್ತನವು ಸಮಾನವಾಗಿದ್ದರೆ -1:
      • ಈ ಅಕ್ಷರವನ್ನು ಹಿಂತಿರುಗಿ
  4. ಕಾರ್ಯ ಸಿಂಟ್ಯಾಕ್ಸ್ ನಿರ್ವಹಿಸಲು '-' ಹಿಂತಿರುಗಿ
  5. ಫಲಿತಾಂಶವನ್ನು ಮುದ್ರಿಸಿ

ಫೈಂಡ್ ದಿ ಡಿಫರೆನ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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;
}

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

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

ವ್ಯತ್ಯಾಸವನ್ನು ಕಂಡುಕೊಳ್ಳುವ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಉದ್ದ ಸ್ಟ್ರಿಂಗ್‌ನ N = ಗಾತ್ರ, ಅವುಗಳ ಅಕ್ಷರ ಆವರ್ತನಗಳನ್ನು ನವೀಕರಿಸಲು ನಾವು ಒಮ್ಮೆ ಎರಡೂ ತಂತಿಗಳ ಮೂಲಕ ಸಂಚರಿಸುತ್ತೇವೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1). ಅಕ್ಷರಗಳನ್ನು ಅವುಗಳ ಆವರ್ತನಗಳೊಂದಿಗೆ ಸಂಗ್ರಹಿಸಲು ನಾವು ಹ್ಯಾಶ್‌ಟೇಬಲ್ ಅನ್ನು ಬಳಸುತ್ತಿದ್ದರೂ, ಇನ್ಪುಟ್ ಅನ್ನು ಲೆಕ್ಕಿಸದೆ ನಾವು ಸ್ಥಿರ ಸ್ಥಳವನ್ನು ಬಳಸುತ್ತೇವೆ. ಆದ್ದರಿಂದ, ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ.