বৈধ আনগ্রামসমূহ


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক গোল্ডম্যান শ্যাস গুগল মাইক্রোসফট নাগরো
এক শব্দের বর্ণসমূহের স্থানপরিবর্তন দ্বারা ভিন্ন শব্দ গঠন হ্যাশ

"বৈধ আনাগ্রাম" সমস্যাটিতে আমরা দুটি দিয়েছি স্ট্রিং str1 এবং str2। উভয় স্ট্রিং অ্যানগ্রাগম কিনা তা সন্ধান করুন। যদি তারা anagrams সত্য সত্য অন্যথায় মিথ্যা ফিরে।

উদাহরণ

ইনপুট:

str1 = "অ্যাব্যাকব্যাক"

str2 = "abbcc"

আউটপুট:

সত্য

ব্যাখ্যা:

যেহেতু str2 টি str1 এর সমস্ত শব্দকে পুনর্বিন্যাস করে গঠিত হতে পারে তাই আউটপুট হবে "সত্য "।

অ্যালগরিদম

  1. উভয় স্ট্রিংয়ের দৈর্ঘ্য সন্ধান করুন
  2. উভয় স্ট্রিং বর্ণমালা অনুসারে বাছাই করুন
  3. উভয় স্ট্রিং তুলনা করুন
  4. সমান ফেরত দিলে "সত্য" অন্যথায় ফিরে "মিথ্যা"

ব্যাখ্যা

আনাগ্রামগুলি একই শব্দ যা একটি ক্রমে সাজানো যেতে পারে যাতে উভয় স্ট্রিং একইরকম দেখায় এবং সেগুলি পুনরায় সাজানোর পরে একক এবং অভিন্ন শব্দ তৈরি করে।

উদাহরণস্বরূপ: নীরব শব্দটি যা একটি ক্রমে সাজানো এবং একটি শব্দ শোনার জন্য তৈরি করা যায়, তাই উভয় শব্দই একে অপরের অ্যানগ্রগ্রাম।

আমাদের কোডটি প্রদত্ত স্ট্রিংগুলি বৈধ কিনা তা খুঁজে বের করতে হবে anagrams বা না, সুতরাং আমাদের মূল ধারণাটি প্রথমে স্ট্রিংয়ের দৈর্ঘ্য সন্ধান করা, যদি উভয় স্ট্রিংয়ের দৈর্ঘ্য সমান হয় তবে কেবল আমরা আরও এগিয়ে চলেছি, অন্যথায় নয়, কারণ স্ট্রিংগুলি দৈর্ঘ্য হলে অ্যানগ্রামগুলি হতে পারে না অনুরূপ নয়। সুতরাং সেখান থেকে, আমরা মিথ্যা ফিরে।

আমাদের পরবর্তী যুক্তি হ'ল এগুলিকে আরোহী ক্রমে সাজানো যাতে প্রতিটি অক্ষর যথাযথভাবে আসে, সুতরাং আমরা একটি ক্রিয়াটি "সাজানো" সংজ্ঞায়িত করেছি। উভয় স্ট্রিং যা বাছাই ফাংশনে অস্থায়ী অ্যারেতে রূপান্তরিত হয় যা অ্যারেটিকে বাছাই করে স্ট্রিংটি str1 তে ফিরিয়ে আনবে, সুতরাং একই স্ট্রিংয়ে সাজানো স্ট্রিং স্ট্রিং স্টোরটি একই স্ট্রিংয়ের সাথে ঘটবে, এবং আমরা বাছাই করা স্ট্রিংগুলি পাই।

নীরব = [গুলি, আমি, ল, ই, এন, টি] // চরিত্রের অ্যারে
শোনো = [l, i, s, t, e, n] // চরিত্রের অ্যারে

বাছাই করা অ্যারে = [ই, আমি, ল, এন, এস, টি] // সাজানো অ্যারে অ্যারে
বাছাই করা অ্যারে = [ই, আই, এল, এন, এস, টি] // সাজানো অ্যারের শৃঙ্খলাগুলি 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 স্ট্রিংয়ের আকার। এখানে আমরা অক্ষরটির ভিত্তিতে স্ট্রিংটি সাজিয়ে রাখি যা সময় লাগবে।

স্পেস জটিলতা ity

ও (1) কারণ আমরা এখানে কোনও অতিরিক্ত স্থান ব্যবহার করি না।