സാധുവായ അനഗ്രാമുകൾ  


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഗോൾഡ്മാൻ സാക്സ് ഗൂഗിൾ മൈക്രോസോഫ്റ്റ് നാഗാരോ
അനഗ്രാം ഹാഷിംഗ്

“സാധുവായ അനഗ്രാമുകൾ” എന്ന പ്രശ്‌നത്തിൽ ഞങ്ങൾ രണ്ട് നൽകി സ്ട്രിംഗുകൾ str1, str2 എന്നിവ. രണ്ട് സ്ട്രിംഗുകളും അനഗ്രാമുകളാണോ അല്ലയോ എന്ന് കണ്ടെത്തുക. അവർ ഉണ്ടെങ്കിൽ അനഗ്രാമുകൾ ശരിയിലേക്ക് മടങ്ങുക അല്ലെങ്കിൽ തെറ്റായി മടങ്ങുക.

ഉദാഹരണം  

ഇൻപുട്ട്:

str1 = "abcbac"

str2 = "aabbcc"

ഔട്ട്പുട്ട്:

യഥാർഥ

വിശദീകരണം:

Str2 ന്റെ എല്ലാ പദങ്ങളും പുന ran ക്രമീകരിക്കുന്നതിലൂടെ str1 രൂപീകരിക്കാൻ‌ കഴിയുന്നതിനാൽ‌ output ട്ട്‌പുട്ട് ആയിരിക്കും "true ”.

അൽഗോരിതം  

  1. രണ്ട് സ്ട്രിംഗിന്റെയും നീളം കണ്ടെത്തുക
  2. സ്ട്രിംഗ് രണ്ടും അക്ഷരമാലാക്രമത്തിൽ അടുക്കുക
  3. രണ്ട് സ്ട്രിംഗും താരതമ്യം ചെയ്യുക
  4. തുല്യ വരുമാനം ഉണ്ടെങ്കിൽ “ശരി” അല്ലെങ്കിൽ മടങ്ങുക "തെറ്റായ"

വിശദീകരണം  

രണ്ട് സ്ട്രിംഗുകളും സമാനമായി കാണപ്പെടുന്ന ക്രമത്തിൽ ക്രമീകരിക്കാൻ കഴിയുന്ന അതേ പദങ്ങളാണ് അനാഗ്രാമുകൾ, അവ പുന ran ക്രമീകരിച്ചതിന് ശേഷം ഒറ്റവും സമാനവുമായ ഒരു വാക്ക് ഉണ്ടാക്കുന്നു.

ഉദാ: നിശബ്ദത എന്നത് ഒരു ക്രമത്തിൽ ക്രമീകരിക്കാനും ഒരു വാക്ക് ശ്രവിക്കാനും കഴിയുന്ന പദമാണ്, അതിനാൽ രണ്ട് വാക്കുകളും പരസ്പരം അനഗ്രാമുകളാണ്.

തന്നിരിക്കുന്ന സ്ട്രിംഗുകൾക്ക് സാധുതയുണ്ടോയെന്ന് കണ്ടെത്തുക എന്നതാണ് ഞങ്ങളുടെ കോഡ് അനഗ്രാമുകൾ അല്ലെങ്കിൽ അല്ല, അതിനാൽ ആദ്യം സ്ട്രിംഗിന്റെ നീളം കണ്ടെത്തുക എന്നതാണ് ഞങ്ങളുടെ പ്രധാന ആശയം, രണ്ട് സ്ട്രിംഗിന്റെയും നീളം സമാനമാണെന്ന് കണ്ടെത്തിയാൽ ഞങ്ങൾ കൂടുതൽ മുന്നോട്ട് പോകും, ​​അല്ലാത്തപക്ഷം, കാരണം സ്ട്രിംഗുകളുടെ ദൈർഘ്യം അനഗ്രാമുകളാകാൻ കഴിയില്ല. സമാനമല്ല. അതിനാൽ അവിടെ നിന്ന് ഞങ്ങൾ തെറ്റായി മടങ്ങുന്നു.

ഞങ്ങളുടെ അടുത്ത യുക്തി അവയെ ആരോഹണ ക്രമത്തിൽ ക്രമീകരിക്കുക എന്നതാണ്, അതിലൂടെ ഓരോ പ്രതീകവും ക്രമത്തിൽ വരുന്നു, അതിനാൽ ഞങ്ങൾ “അടുക്കുക” എന്ന ഒരു ഫംഗ്ഷൻ നിർവചിച്ചു. സോർട്ട് ഫംഗ്ഷനിലേക്ക് കൈമാറുന്ന രണ്ട് സ്ട്രിംഗുകളും ഒരു താൽക്കാലിക അറേയിലേക്ക് പരിവർത്തനം ചെയ്യുന്നു, അത് അറേ അടുക്കി സ്ട്രിംഗ് സ്ട്രിംഗ് 1 ആക്കി മാറ്റാൻ പോകുന്നു, അതിനാൽ സ്ട്രിംഗ് ഒരേ സ്ട്രിംഗിൽ സംഭരിച്ച സ്ട്രിംഗ് സ്റ്റോർ, ഇത് രണ്ട് സ്ട്രിംഗുകളിലും സംഭവിക്കും, അടുക്കിയ സ്ട്രിംഗുകൾ നമുക്ക് ലഭിക്കും.

ഇതും കാണുക
ഹ്രസ്വമായ പലിൻഡ്രോം

നിശബ്ദ = [s, i, l, e, n, t] // പ്രതീക ശ്രേണി
കേൾക്കുക = [l, i, s, t, e, n] // പ്രതീക ശ്രേണി

അടുക്കിയ അറേ = [e, i, l, n, s, t] // സ്ട്രിംഗ് 1 ൽ സംഭരിച്ചിരിക്കുന്ന നിശബ്ദതയുടെ അടുക്കിയ ശ്രേണി
അടുക്കിയ അറേ = [e, i, l, n, s, t] // str2- ൽ സംഭരിച്ചിരിക്കുന്ന ശ്രവണ ശ്രേണി

ഫോർ ലൂപ്പിനൊപ്പം രണ്ട് സ്ട്രിംഗുകളുടെയും ഓരോ സൂചികയും ഒരേ പ്രതീകങ്ങൾ സമാനമാണെന്ന് കണ്ടെത്തിയാൽ ഞങ്ങൾ താരതമ്യം ചെയ്യും, എന്നിട്ട് അവ അനഗ്രാമുകളാണ്, അവ ശരിയാണെങ്കിൽ “ട്രൂ” പ്രിന്റുകളും തെറ്റായ പ്രിന്റുകളും തെറ്റായി മടക്കിനൽകുന്നു.

നടപ്പിലാക്കൽ  

സാധുവായ അനഗ്രാമുകൾക്കായുള്ള സി ++ പ്രോഗ്രാം

#include <iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

bool areAnagram(string str1, string str2)
{
    //getting length of both the strings
    int n1 = str1.length();
    int n2 = str2.length();

    //Checking if both the strings are of same length
    if (n1 != n2)
        return false;

    //Sorting both the string alphabetically
    sort(str1.begin(), str1.end());
    sort(str2.begin(), str2.end());

    //checking each character of string is equal to
    //another character of string
    if (str1 != str2)
        return false;

    return true;
}

int main ()
{
    string str1 = "silent";
    string str2 = "listen";
    if(areAnagram(str1,str2))
        cout << "true";
    else
        cout << "false";
    return 0;
}
true

സാധുവായ അനഗ്രാമുകൾക്കായുള്ള ജാവ പ്രോഗ്രാം

import java.util.Arrays;
import java.util.Scanner;
class validAnagrams
{
  public static String sort(String str)
  {
      char temp[] = str.toCharArray();
      Arrays.sort(temp);
      return new String(temp);
  }
  public static boolean areAnagram(String str1, String str2)
  {
    //getting length of both the strings
    int length1 = str1.length();
    int length2 = str2.length();

    //Checking if both the strings are of same length
    if (length1 != length2)
    {
      return false;
    }

    //Sorting both the string alphabetically
    str1=sort(str1);
    str2=sort(str2);

    //checking each character of string is equal to
    //another character of string
    for (int i = 0; i < length1; i++)
    {
        if (str1.charAt(i) != str2.charAt(i))
        {
            return false;
      }
    }

        return true;
    }
  public static void main(String [] args)
  {
    String str1 = "silent";
    String str2 = "listen";
    System.out.println(areAnagram(str1,str2)?"true":"false");

  }
}
true

സാധുവായ അനഗ്രാമുകൾക്കായുള്ള സങ്കീർണ്ണത വിശകലനം  

സമയ സങ്കീർണ്ണത

O (nlogn) എവിടെ n സ്ട്രിംഗിന്റെ വലുപ്പമാണ്. ഇവിടെ നമ്മൾ സ്ട്രിംഗ് തരംതിരിക്കുന്നത് പ്രതീകത്തിന്റെ അടിസ്ഥാനത്തിലാണ്.

ഇതും കാണുക
നൽകിയ സംഖ്യകളെ ഏറ്റവും വലിയ സംഖ്യയായി ക്രമീകരിക്കുക

ബഹിരാകാശ സങ്കീർണ്ണത

O (1) കാരണം ഞങ്ങൾ ഇവിടെ അധിക സ്ഥലമൊന്നും ഉപയോഗിക്കുന്നില്ല.