유효한 아나그램  


난이도 쉽게
자주 묻는 질문 아마존 골드만 삭스 구글 Microsoft 나가로
철자 바꾸기 해싱

“Valid Anagrams”문제에서 우리는 문자열 str1 및 str2. 두 문자열이 모두 애너그램인지 아닌지 확인하십시오. 그들이 있다면 아나 그램 true를 반환하고 그렇지 않으면 false를 반환합니다.

예  

입력:

str1 = "abcbac"

str2 =“aabbcc”

출력:

참된

설명 :

str2는 str1의 모든 단어를 재정렬하여 형성 할 수 있으므로 출력은 "진실".

암호알고리즘  

  1. 두 문자열의 길이를 찾으십시오.
  2. 두 문자열을 알파벳순으로 정렬
  3. 두 문자열 비교
  4. 동등한 수익 인 경우 "진실" 그렇지 않으면 반환 "그릇된"

설명  

아나그램은 두 문자열이 비슷하게 보이는 순서로 정렬 할 수있는 동일한 단어로, 다시 정렬 한 후 하나의 동일한 단어를 만듭니다.

예 : 무음은 순서대로 정렬되어 단어를들을 수있는 단어이므로 두 단어는 서로의 철자입니다.

우리의 코드는 주어진 문자열이 유효한지 확인하는 것입니다. 아나 그램 그래서 우리의 주된 아이디어는 먼저 문자열의 길이를 찾는 것입니다. 만약 두 문자열의 길이가 비슷하다면 우리는 더 멀리 움직일뿐입니다. 그렇지 않으면 그렇지 않습니다. 비슷하지 않습니다. 그래서 거기에서 우리는 거짓을 반환합니다.

다음 논리는 오름차순으로 정렬하여 각 문자가 순서대로 오도록하는 것이므로 "정렬"함수를 정의했습니다. 정렬 함수에 전달 된 두 문자열은 모두 임시 배열로 변환되어 배열을 정렬하고 문자열을 str1로 반환하므로 정렬 된 문자열은 동일한 문자열에 문자열을 저장합니다. 두 문자열 모두에서 발생합니다. 정렬 된 문자열을 얻습니다.

참조
최단 회문

silent = [s, i, l, e, n, t] // 문자 배열
listen = [l, i, s, t, e, n] // 문자 배열

sorted array = [e, i, l, n, s, t] // str1에 저장된 무음의 정렬 된 배열
sorted array = [e, i, l, n, s, t] // str2에 저장된 청취의 정렬 된 배열

그런 다음 for 루프를 사용하여 동일한 문자가 동일한 것으로 확인되면 두 문자열의 모든 단일 인덱스를 비교합니다. 그러면 애너그램이고 true 및 "true"인쇄를 반환하고 false가 반환되면 false 인쇄를 반환합니다.

실시  

유효한 아나그램을위한 C ++ 프로그램

#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 문자열의 크기입니다. 여기서는 nlogn 시간이 걸리는 문자를 기준으로 문자열을 정렬합니다.

참조
주어진 숫자를 배열하여 가장 큰 숫자를 만듭니다.

공간 복잡성

O (1) 여기에 추가 공간을 사용하지 않기 때문입니다.