• #### 科普

SCIENCE

#### 英语

ENGLISH

#### 科技

TECHNOLOGY

MOVIE

FOOD

#### 励志

INSPIRATIONS

#### 社会

SOCIETY

TRAVEL

#### 动物

ANIMALS

KIDS

#### 卡通

CARTOON

#### 计算机

COMPUTER

#### 心理

PSYCHOLOGY

#### 教育

EDUCATION

#### 手工

HANDCRAFTS

#### 趣闻

MYSTERIES

CAREER

GEEKS

#### 时尚

FASHION

• 精品课
• 公开课
• 欢迎下载我们在各应用市场备受好评的APP

点击下载Android最新版本

点击下载iOS最新版本 扫码下载译学馆APP

#### 数据结构：变位词问题的解法

Data Structures: Anagram Problem Solution

Hi, I’m Gayle Laakmann McDowell, author of Cracking the Coding Interview.

Today I’m going to solve a problem called making anagrams.

This problem goes as follows: You have

two strings, just with the lowercase characters, “a” to “z”,

how many characters would you have to remove from the two strings to make them anagrams?

So, anagrams as you might remember are just permutations of a word,

so rearrangements of the words.

So for two words to be anagrams it means that they have the same characters but just

in different orders. So for example you have the input
hello和billion 你一共需要去掉6个字符：hello中的“h”和“e”
hello and billion you’d have to remove six characters total – the “h” and the “e” from
billion中的“b” “i” “i” “n” 然后这两个字符串
hello and the “b” “i” “i” “n” from billion and then that will leave you with “l” “l” and “o”

in each of the two strings. So given two arbitrary strings how many characters

would you have to remove from each string to make them anagrams? Well anagrams are..

…they have the same exact characters and the same number of each characters,

without the order mattering. So if you want to know…if you have just

the string “a” “a” “a” and “a” and you want to make those two things anagrams of each

other, you’d have to remove 2 a’s from the first string.

So if we have a whole bunch of characters it’s the same process essentially,

if we want to make two

strings anagrams of each other, count how many times each character appears in each

string and then look at the difference between those values. So let’s turn to

the code now. So I already have a main function written that handles my input,

so now I just need to write this function. Okay. What the logic here is

going to be is just count how many times each character appears, and then

get the delta between these. So int charcount1 is going to be – I’ll

just push this off to another function I’m not going to write it right now –
——“getCharCount(first)” 对第二个字符串也执行相同的操作
get char counts of first. Then, I do basically the same thing for the second

string and then I return the delta between these. Okay. So note here that I’ve

been pretty aggressive with modularization. That’s kind of a good thing to do in order to

show great coding style.

Okay, now let’s turn to how get char works, get char counts works.

So, that’s going to take in a string, I’ll just call it “s,”

and it’s going to create, so it’s gonna

need an array with one slot for each letter.

So I’m going to call this charCounts

and it’s going to be a size number of letters

and then it’s going to go through each string,

each character, and so for int i equals 0
i < s.length();
i less than s dot length,
i++)”
i++
“char c = s.charAt(i);”
char c equals s dot char at i.

And then I need to convert like “a” to 0, “b” to 1, “c” to 2 etc.

So one way of doing that is I get the offset

so I can take the character “a”

and convert that to its ASCII code.

Then the character “b” will be the next integer.

So in Java we can kind of treat integers,

you can treat characters sort of as integers and so

doing this will get the character value of “a”

so, if I do “b” minus “a” I’d actually get 1.

So the code here is going to be

this character “c” minus this offset

and then so that’s going to give me like “a” to 0, “b” to 1, “c” to 2 etc.

then I just need to increment the value of that code and return that array.

My final method is this getDelta function

and it’s going to take in

two strings, two arrays,

and compute the delta between each value.

So,

I’ll do some very basic error handling right now.

In an ideal world I should probably, you know, throw an exception at that,

but I’m just going to give it a negative one, so the arrays need to be the same length.

Okay,

now I just need to walk through each value in the arrays

and compute the absolute value of their differences.

So,
“math.abs(array1[i]
math dot absolute value of array of 1 of
-array2[i])”
i minus array 2 of i

and delta plus equals difference return delta.

Okay, now let’s see how this works.

I’ll run this.

Alright! We passed our test cases, that’s fantastic. I’ll try a slightly more advanced one.

Looks like we’re doing great, so let’s review how our code works.

So we have this number needed function

and it counts how many times each character appears in each string

and then it walks through the two counts and computes the difference of it.

So, to get the number of characters in each string, that’s pretty easy,

we just use a simple array will be sufficient here.

If we had a bigger variety of strings or characters,

some other slightly different data set, we might want to use a hashmap instead.

Our integer array is sufficient here.

and then we walk through and get the delta between each value in each array.

Now we need to know again that it’s the same length.

So that’s, you know, this is a pretty straightforward problem.

One tip that’s useful in a lot of problems and was useful here

is to really define and think about what exactly does it take to

make two things anagrams, and the algorithm sort of follows from that explanation.

So keep that in mind for your future problems.

Good luck.

[B]hugue