Prerequisite:

先決條件：

• Hashing data structure

  散列數(shù)據(jù)結(jié)構(gòu)

Problem statement:

問題陳述：

Find the minimum number of steps to make two strings Anagram. Both strings are of the same length and the lower case. At each step, you can convert any character to string t to any other character.

找到使兩個字符串Anagram最少的步驟數(shù)。 兩個字符串的長度相同，并且都小寫。 在每個步驟中，您都可以將字符串t中的任何字符轉(zhuǎn)換為其他任何字符。

Example:

例：

Example 1: String s= "bba" String t= "aab"Minimum number of steps to make two strings anagram: 1 String t can be converted to "bab" which is anagram of string s="bba"Example 2: String s= "coding" String t= "coders"Minimum number of steps to make two strings anagram: 3 String t can be converted to "coding" which is anagram of string s="coding"(basically here we need to convert into same string)

Solution:

解：

We can solve the problem by using hashing. Two strings are said to be an anagram of each other if both have the same set of characters with equal frequency.

我們可以通過使用哈希解決問題。 如果兩個字符串都具有相同的頻率相同的字符集，則稱這兩個字符串為彼此的字謎。

Now since both of the string is of the same length it's often possible to convert the string t to the string s. We can solve this by using a hashing and greedy algorithm.
Firstly we calculate two hash tables for both the strings s & t to store the frequencies for each character.

現(xiàn)在，由于兩個字符串的長度相同，因此通常可以將字符串t轉(zhuǎn)換為字符串s 。 我們可以通過使用哈希和貪婪算法來解決此問題。
首先，我們?yōu)樽址畇 ＆ t計算兩個哈希表，以存儲每個字符的頻率。

Let's say namely table1 and table2

比方說table1和table2

Both the table have 26 entries corresponding to 26 lowercase letters. The hash function that is used is: f(x)=x-'a' and instead of storing the characters itself we store the frequency like below:

兩個表都有26個對應于26個小寫字母的條目。 使用的哈希函數(shù)是：f(x)= x-'a'，而不是存儲字符本身，我們存儲頻率如下：

Set table1[26]={0} to store frequencies for string s

將table1 [26] = {0}設(shè)置為存儲字符串s的頻率

Set table2[26]={0} to store frequencies for string t

將table2 [26] = {0}設(shè)置為存儲字符串t的頻率

for(int i=0;i<s.length();i++)table1[s[i]-'a']++;table2[t[i]-'a']++; end for

Now after this both the table have 26 characters('a' to 'z') which have values 0(in case the character doesn't exist) or non-zero. Now, as the strings are of equal length it's guaranteed that string t can be converted so that it becomes an anagram of string s.

現(xiàn)在，在這之后，兩個表都包含26個字符(“ a”至“ z”)，其值均為0(以防字符不存在)或非零。 現(xiàn)在，由于字符串長度相等，因此可以保證可以將字符串t轉(zhuǎn)換為字符串s的字謎。

So for each character(index in table) there can be three cases

因此，對于每個字符(表中的索引)可以有三種情況

For i =0 to 26

對于i = 0到26

table1[i]=table2[i]

table1 [i] = table2 [i]

Then no need to do anything as we need minimum no of conversion

然后，無需做任何事情，因為我們需要最少的轉(zhuǎn)換次數(shù)

table2[i]>table1[i]

table2 [i]> table1 [i]

That means string

這意味著字符串

t has more number of same characters than in string s. Since in anagram both will the have same frequency for any character thus we need to convert the additional table2[i]-table1[i] to some other characters (not necessary to only one character)

t具有比字符串s中更多的相同字符。 由于在字謎中，兩個字符的頻率都相同，因此我們需要將附加的table2 [i] -table1 [i]轉(zhuǎn)換為其他字符(不必僅轉(zhuǎn)換為一個字符)

table2[i]<table1[i]

table2 [i] <table1 [i]

That means string

這意味著字符串

t has less number of same characters than in string s. Since in anagram both will the have same frequency for any character thus we have a deficiency of (table1[i]-table2[i]) number of characters which need to be converted from rest of the excess characters (which found in the second)

t的相同字符數(shù)少于字符串s中的相同字符數(shù)。 由于在字謎中，兩個字符的頻率都相同，因此我們?nèi)鄙?table1 [i] -table2 [i])個字符，需要從其余多余字符(在第二個字符中找到)進行轉(zhuǎn)換

So what is the minimum number of steps required?

那么，最少需要多少步？

It's basically sum(table2[i]-table1[i]) if table2[i]-table1[i] Set Steps=0 For i=0 to 25If(table2[i]>table1[i])Steps+= table2[i]-table1[i] End forOr For i=0 to 25If(table1[i]>table2[i])Steps+= table1[i]-table2[i] End for

Both algorithms will give the same result as both are anagrams of each other. But sticking to the question we are assuming that we are converting string t following the convention that if for any character the frequency in t ?is greater than s ?then we need to convert the extra characters which have deficiency string t.

兩種算法的字謎結(jié)果都相同。 但是，堅持這個問題，我們假設(shè)要按照以下約定轉(zhuǎn)換字符串t ：如果對于任何字符， t中的頻率大于s，則需要轉(zhuǎn)換具有不足字符串t的多余字符。

#include <bits/stdc++.h> using namespace std;int minSteps(string s, string t) {int mymap1[26] = { 0 };int mymap2[26] = { 0 };for (int i = 0; i < s.length(); i++) {mymap1[s[i] - 'a']++;mymap2[t[i] - 'a']++;}int count = 0;for (int i = 0; i < 26; i++) {if (mymap2[i] > mymap1[i])count += mymap2[i] - mymap1[i];}return count; }int main() {cout << "Enter string, s:\n";string s;cin >> s;cout << "Enter string, t:\n";string t;cin >> t;cout << "Minimum number of steps needed : " << minSteps(s, t) << endl;return 0; }

Output:

輸出：

RUN 1: Enter string, s: abb Enter string, t: baa Minimum number of steps needed : 1RUN 2: Enter string, s: coders Enter string, t: coding Minimum number of steps needed : 3

翻譯自: https://www.includehelp.com/data-structure-tutorial/minimum-number-of-steps-to-make-two-strings-anagram.aspx

總結(jié)

以上是生活随笔為你收集整理的制作两个字符串字谜的最小步骤数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。