תרשימים תקפים


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית גולדמן זאקס Google מיקרוסופט נגארו
אֲנַגְרַמָה חבטות

בבעיה "תרשימים תקפים" הבאנו שניים מחרוזות str1 ו- str2. גלה ששני המיתרים הם אנגרמות או לא. אם הם אנגרמות להחזיר נכון אחרת להחזיר שקר.

דוגמה

קלט:

str1 = "abcbac"

str2 = "aabbcc"

פלט:

נכון

הסבר:

מכיוון ש- str2 יכול להיווצר על ידי סידור מחדש של כל המילים str1 כך שהפלט יהיה "נָכוֹן".

אַלגוֹרִיתְם

  1. מצא את אורך שני המיתרים
  2. למיין את שני המיתרים באלף בית
  3. השווה את שני המיתרים
  4. אם תשואה שווה "נָכוֹן" אחרת לחזור "שֶׁקֶר"

הסבר

אנגרמות הן אותן מילים שניתן לסדר לפי סדר בו שני המיתרים נראים דומים ויוצרים מילה אחת וזהה לאחר סידורם מחדש.

לדוגמא: שקט היא המילה שניתן לסדר לפי סדר ולהפוך מילה להאזנה, כך ששתי המילים הן אנגרמות זו לזו.

הקוד שלנו הוא למצוא אם המחרוזות הנתונות תקפות אנגרמות או לא, אז הרעיון העיקרי שלנו הוא למצוא תחילה את אורך המחרוזת, אם אורכו של שני המיתרים נמצא דומה אז רק אנו מתקדמים הלאה, אחרת לא, מכיוון שמחרוזות אינן יכולות להיות האנגרמות אם אורכן הוא לא דומה. אז משם, אנחנו חוזרים כוזבים.

ההיגיון הבא שלנו הוא לסדר אותם בסדר עולה כך שכל תו יבוא לפי הסדר, ולכן הגדרנו פונקציה "מיון". שתי המחרוזות שעוברות לפונקציית המיון מומרות למערך זמני אשר הולך למיין את המערך ולהחזיר את המחרוזת ל- str1, ולכן מחרוזת ממוינת המאוחסנת במאגר המחרוזות באותה מחרוזת, זה יקרה בשני המיתרים, ואנחנו מקבלים את המיתרים הממוינים.

שקט = [s, i, l, e, n, t] // מערך תווים
האזן = [l, i, s, t, e, n] // מערך תווים

מערך ממוין = [e, i, l, n, s, t] // מיון מערך של שקט המאוחסן ב- str1
מערך ממוין = [e, i, l, n, s, t] // מערך מיון של האזנה המאוחסן ב- str2

ואז עם לולאת ה- for נשווה כל אינדקס אחד של שני המיתרים אם אותם תווים יימצאו זהים, אז הם אנגרמות ומחזירים הדפסים אמיתיים ו"אמיתיים "והדפסים כוזבים אם הוא מוחזר כוזב.

יישום

תוכנית 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

תוכנית Java לאנגרמות תקפות

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) כי אנחנו לא משתמשים בשטח נוסף כאן.