有效字谜


难度级别 易得奖学金
经常问 亚马逊 高盛 谷歌 微软 长郎
字谜 哈希

在“有效字谜”问题中,我们给出了两个 字符串 str1和str2。 找出两个字符串是否是字谜。 如果他们是 字谜 返回true,否则返回false。

使用案列

输入:

str1 =“ abcbac”

str2 =“ aabbcc”

输出:

true

说明:

由于可以通过重新排列str2的所有单词来形成str1,因此输出为 真的”。

算法

  1. 查找两个字符串的长度
  2. 按字母顺序对字符串进行排序
  3. 比较两个字符串
  4. 如果收益相等 “真正” 否则返回 “错误的”

说明

字谜是可以按照两个字符串看起来相似的顺序排列的相同词,并在重新排列它们后形成一个相同的词。

例如:无声是可以按顺序排列并让一个单词收听的单词,因此两个单词都是彼此的字谜。

我们的代码是查找给定的字符串是否有效 字谜 还是不,所以我们的主要思想是首先找到字符串的长度,如果发现两个字符串的长度相似,则只有我们进一步走下去,否则就不行了,因为如果字符串的长度是不相似。 因此,从那里,我们返回false。

我们的下一个逻辑是按升序排列它们,以便每个字符都按顺序排列,因此我们定义了一个函数“ sort”。 传递给sort函数的两个字符串都转换为一个临时数组,该数组将对该数组进行排序并将字符串返回到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

适用于有效字谜的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(登录) 哪里 n 是字符串的大小。 在这里,我们根据需要花费登录时间的字符对字符串进行排序。

空间复杂度

O(1) 因为我们在这里不使用任何多余的空间。