Data structures Anagram Queries using Hashing In this assignment you will implem
ID: 3867182 • Letter: D
Question
Data structures
Anagram Queries using Hashing
In this assignment you will implement a program which prints out all anagrams of a specified string. Two strings are anagrams of one another if by rearranging letters of one of the strings you can obtain another. For example, the string "stuart" is an anagram of "rattus". For the purpose of this assignment, we are only interested in those anagrams of a given string which appear in the dictionary. The dictionary you should use is the file attached words.txt.
Algorithm and Implementation:
Since we will be performing multiple anagram queries, our first step is to load all of the (~25,000) words in the dictionary into an appropriate data structure. A primary requirement is that one must be able to efficiently search this data structure to look for anagrams of a given word. A clever trick that we will use to facilitate this is to first sort the letters of every word we insert into our data structure (you may use any sort you wish -- even one from the Java API) to produce a key for each word. For example, the key for the string "stuart" is "arsttu", similarly the key for both "star" and "rats" is "arst". (Expert Scrabble players will recognize this procedure as computing the alphagram of a set of letters). We will then use a hash table to store pairs of strings, where the pair consists of the original word and its key. You must write a little class to represent this pair of strings (perhaps call it Anagram).
When performing insertions into the hash table, we will compute the hash value of the key/alphagram of the word to compute the correct bucket (location in the hash table). This approach guarantees that all words which are anagrams of one another are stored in the same bucket of the hash table. Similarly, when we are searching for anagrams, we will first compute the key of the word we are searching for, then hash the key, then search that bucket for anagram matches. You should feel free to use the methods described in the text and in class for appropriate hash functions for hashing strings (please cite any source which you use). Also, make sure your function is efficient and does not hash completely unrelated sets of anagrams to the same bucket *if possible*. If it does, handle the collisions as you see fit (Open Addressing,
Chaining, whatever -- BTW: you may use the Java API for your linked list(s) if you go that route). Also note that if you must probe for a given set of anagrams in time greater than or equal to O(log2n), then you must revise your hash function. You will be graded heavily on the performance of your function. NOTE: you are *NOT* allowed to use the hashCode method from the String class to do your work -- you must write your own hash function. Furthermore, you are NOT allowed to use the Java API (Hashtable/HashMap/HashSet) for your hash table -- you need to create an array for that.
Your code should contain features to count how many collisions occur when placing words from the dictionary into your hash table. At program completion, report how many words were placed and how many collisions occurred. This output will be to the monitor/console (System.out). Any time you try and place a word and the hash table has a word at that location that does NOT have the same key, that counts as a collision.
Details:
The hash table code which you provide only needs to have the minimum functionality necessary for this assignment (it does not have to be generic). You should fix a size for your hash table for efficient searching. For debugging your code, you should work with a much smaller practice dictionary, perhaps 10 words, and a much smaller hash table, perhaps 15-20 buckets (depending on whether or not there are any anagrams in the dictionary). Make sure your table size is prime to help reduce collisions. Remember it is ok to sacrifice space for speed -- that is what hashing is all about. That said, your table should not be bigger than 200,000. Try different table sizes in conjunction with your hash function. Modify the table size and/or function accordingly until you reach a 'sweet spot' (a threshold value). You can decide a threshold value.
NOTE: You may disregard any words in the dictionary which contain any punctuation characters. All other words should be included. Also, you should convert any uppercase characters to lowercase (thus you are only representing words that contain all lower case characters). Your program should read anagram queries from a file which has been specified as a command line argument. Each query in the file will be on its own line and will simply consist of a string. The output file (which will also be specified on the command line following the input file) should contain the original string, then the number of matching anagrams, followed by those anagrams. Look at the example input file and the resulting output file. Your output file should match this format exactly, except that the matching anagrams you output may be ordered differently. If run from the command line, executing your program would be done as follows: java HashTester input_file.txt output_file.txt
NOTE: Do not count a word as an anagram of itself.
To Turn In (in an appropriately named zip): All source files (name your tester file -- the one that contains the main method -- HashTester)
the words file (the dictionary of words) the *ROBUST* input file you used for testing the output file your program produced. Include a comment at the top of your Tester file that *clearly* describes how you confirmed your hashing function operated better than O(log2n). Another way to show your hash function is good is to compare it with the API's String hashCode() - if you do better than it does, you are good to go! If you fail to justify that your hash function was better than O(log2n) you will lose 10 points.
EXTRA CREDIT: *Clearly* demonstrate your hash function is better than the Java API's for 10 extra points. Include justification of the extra credit in comments at the top of your tester file.
Output Example One
qiewuro
ssrab
oflg
equiye
Output Example Two
qiewuro 0
ssrab 1 brass
oflg 2 flog golf
equiye 0
Dictionary called words.txt, it is only couple works bc it doesnt let me to post the entire dictionary
10th
1st
2nd
3rd
4th
5th
6th
7th
8th
9th
a
AAA
AAAS
Aarhus
Aaron
AAU
ABA
Ababa
aback
abacus
abalone
abandon
abase
abash
abate
abater
abbas
abbe
abbey
abbot
Abbott
abbreviate
abc
abdicate
abdomen
abdominal
abduct
Abe
abed
Abel
Abelian
Abelson
Aberdeen
Abernathy
aberrant
aberrate
abet
abetted
abetting
abeyance
abeyant
abhorred
abhorrent
abide
Abidjan
Abigail
abject
ablate
ablaze
able
ablution
Abner
abnormal
Abo
aboard
abode
abolish
abolition
abominable
abominate
aboriginal
aborigine
aborning
abort
abound
about
above
aboveboard
aboveground
abovementioned
abrade
Abraham
Abram
Abramson
abrasion
abrasive
abreact
abreast
abridge
abridgment
abroad
abrogate
abrupt
abscess
abscissa
abscissae
absence
absent
absentee
absenteeism
absentia
absentminded
absinthe
absolute
absolution
absolve
absorb
absorbent
absorption
absorptive
abstain
abstention
abstinent
abstract
abstracter
abstractor
abstruse
absurd
abuilding
abundant
abusable
abuse
abusive
abut
abutted
abutting
abysmal
abyss
Abyssinia
AC
academe
academia
academic
academician
academy
Acadia
acanthus
Acapulco
accede
accelerate
accelerometer
accent
accentual
accentuate
accept
acceptant
acceptor
access
accessible
accession
accessory
accident
accidental
accipiter
acclaim
acclamation
acclimate
accolade
accommodate
accompaniment
accompanist
accompany
accomplice
accomplish
accord
accordant
accordion
accost
account
accountant
Accra
accredit
accreditate
accreditation
accretion
accrual
accrue
acculturate
accumulate
accuracy
accurate
accusation
accusative
accusatory
accuse
accustom
ace
acerbic
acerbity
acetate
acetic
acetone
acetylene
ache
achieve
Achilles
aching
achromatic
acid
acidic
acidulous
Ackerman
Ackley
acknowledge
acknowledgeable
ACM
acme
acolyte
acorn
acoustic
acquaint
acquaintance
acquiesce
acquiescent
acquire
acquisition
acquisitive
acquit
acquittal
acquitting
acre
acreage
acrid
acrimonious
acrimony
acrobacy
acrobat
acrobatic
acronym
acropolis
across
acrylate
acrylic
ACS
act
Actaeon
actinic
actinide
actinium
actinolite
actinometer
activate
activation
activism
Acton
actor
actress
Acts
actual
actuarial
actuate
acuity
acumen
acute
acyclic
ad
Ada
adage
adagio
Adair
Adam
adamant
Adams
Adamson
adapt
adaptation
adaptive
add
added
addend
addenda
addendum
addict
Addis
Addison
addition
additional
additive
addle
address
addressee
Addressograph
adduce
Adelaide
Adele
Adelia
Aden
adenine
adenoma
adenosine
adept
adequacy
adequate
adhere
adherent
adhesion
adhesive
adiabatic
adieu
adipic
Adirondack
adjacent
adject
adjectival
adjective
adjoin
adjoint
adjourn
adjudge
adjudicate
adjunct
adjust
adjutant
Adkins
Adler
administer
administrable
administrate
administratrix
admiral
admiralty
admiration
admire
admissible
admission
admit
admittance
admitted
admitting
admix
admixture
admonish
admonition
ado
adobe
adolescent
Adolph
Adolphus
Adonis
adopt
adoption
adoptive
adore
adorn
adposition
adrenal
adrenaline
Adrian
Adriatic
Adrienne
adrift
adroit
adsorb
adsorbate
adsorption
adsorptive
adulate
adult
adulterate
adulterous
adultery
adulthood
advance
advantage
advantageous
advent
adventitious
adventure
adventurous
adverb
adverbial
adversary
adverse
advert
advertise
advice
advisable
advise
advisee
advisor
advisory
advocacy
advocate
Aegean
aegis
Aeneas
Aeneid
aeolian
Aeolus
aerate
aerial
Aerobacter
aerobic
aerodynamic
aerogene
aeronautic
aerosol
aerospace
Aeschylus
aesthete
aesthetic
afar
affable
affair
affect
affectate
affectation
affectionate
afferent
affiance
affidavit
affiliate
affine
affinity
affirm
affirmation
affirmative
affix
afflict
affluence
affluent
afford
afforest
afforestation
affricate
affront
Afghan
Afghanistan
aficionado
afield
afire
aflame
afloat
afoot
aforementioned
aforesaid
aforethought
afoul
afraid
afresh
Africa
afro
aft
aftereffect
afterglow
afterimage
afterlife
aftermath
afternoon
afterthought
afterward
afterword
again
against
Agamemnon
agate
Agatha
agave
age
Agee
agenda
agent
agglomerate
agglutinate
agglutinin
aggravate
aggregate
aggression
aggressive
aggressor
aggrieve
aghast
agile
aging
agitate
agleam
Agnes
Agnew
agnomen
agnostic
ago
agone
agony
agouti
agrarian
agree
agreeable
agreed
agreeing
agribusiness
Agricola
agricultural
agriculture
agrimony
ague
Agway
ah
ahead
ahem
Ahmadabad
Ahmedabad
ahoy
aid
Aida
aide
Aides
Aiken
ail
ailanthus
aile
Aileen
aileron
aim
ain't
Ainu
air
airborne
aircraft
airdrop
airedale
Aires
airfare
airfield
airflow
airfoil
airframe
airlift
airline
airlock
airmail
airman
airmass
airmen
airpark
airplane
airport
airspace
airspeed
airstrip
airtight
airway
airy
aisle
Aitken
ajar
Ajax
AK
Akers
akin
Akron
AL
ala
Alabama
Alabamian
alabaster
alacrity
alai
Alameda
Alamo
Alan
alan
alarm
Alaska
alb
alba
albacore
Albania
Albanian
Albany
albatross
albeit
Alberich
Albert
Alberta
Alberto
Albrecht
Albright
album
albumin
Albuquerque
Alcestis
alchemy
Alcmena
Alcoa
alcohol
alcoholic
alcoholism
Alcott
alcove
Aldebaran
aldehyde
Alden
alder
alderman
aldermen
Aldrich
aldrin
ale
Alec
Aleck
aleph
alert
alewife
Alex
Alexander
Alexandra
Alexandre
Alexandria
Alexei
Alexis
alfalfa
Alfonso
alfonso
Alfred
Alfredo
alfresco
alga
algae
algaecide
algal
algebra
algebraic
Algenib
Alger
Algeria
Algerian
Algiers
alginate
Algol
Algonquin
algorithm
algorithmic
Alhambra
Ali
alia
alias
alibi
Alice
Alicia
alien
alienate
alight
align
alike
alimony
aliphatic
aliquot
Alison
Alistair
alive
alizarin
alkali
alkaline
alkaloid
alkane
alkene
all
Allah
Allan
allay
allegate
allegation
allege
Allegheny
allegiant
allegoric
allegory
Allegra
allegro
allele
allemand
Allen
Allentown
allergic
allergy
alleviate
alley
alleyway
alliance
allied
alligator
Allis
Allison
alliterate
allocable
allocate
allot
allotropic
allotted
allotting
allow
allowance
alloy
allspice
Allstate
allude
allure
allusion
allusive
alluvial
alluvium
ally
allyl
Allyn
alma
Almaden
almagest
almanac
almighty
almond
almost
aloe
aloft
aloha
alone
along
alongside
aloof
aloud
alp
alpenstock
Alpert
alpha
alphabet
alphabetic
alphameric
alphanumeric
Alpheratz
Alphonse
alpine
Alps
already
Alsatian
also
Alsop
Altair
altar
alter
alterate
alteration
altercate
alterman
altern
alternate
althea
although
altimeter
altitude
alto
altogether
Alton
altruism
altruist
alum
alumina
aluminate
alumna
alumnae
alumni
alumnus
alundum
Alva
Alvarez
alveolar
alveoli
alveolus
Alvin
alway
always
alyssum
A&M
am
AMA
Amadeus
amalgam
amalgamate
amanita
amanuensis
amaranth
Amarillo
amass
amateur
amateurish
amatory
amaze
Amazon
ambassador
amber
ambiance
ambidextrous
ambient
ambiguity
ambiguous
ambition
ambitious
ambivalent
amble
ambling
ambrose
ambrosia
ambrosial
ambulant
ambulate
ambulatory
ambuscade
ambush
Amelia
ameliorate
amen
amend
amende
Amerada
America
American
Americana
Americanism
americium
Ames
Ameslan
amethyst
amethystine
Amherst
ami
amicable
amid
amide
amidst
amigo
amino
aminobenzoic
amiss
amity
Amman
Ammerman
ammeter
ammo
ammonia
ammoniac
ammonium
ammunition
amnesia
Amoco
amoeba
amoebae
amok
among
amongst
amoral
amorous
amorphous
amort
Amos
amount
amp
amperage
ampere
ampersand
Ampex
amphetamine
amphibian
amphibious
amphibole
amphibology
amphioxis
ample
amplifier
amplify
amplitude
amply
amputate
amputee
amra
Amsterdam
Amtrak
amulet
amuse
Amy
amy
amygdaloid
an
ana
Anabaptist
Anabel
anachronism
anachronistic
anaconda
anaerobic
anaglyph
anagram
Anaheim
analeptic
analgesic
analogous
analogue
analogy
analyses
analysis
analyst
analytic
anamorphic
anaplasmosis
anarch
anarchic
anarchy
Anastasia
anastigmat
anastigmatic
anastomosis
anastomotic
anathema
Anatole
anatomic
anatomy
ancestor
ancestral
ancestry
anchor
anchorage
anchorite
anchoritism
anchovy
ancient
ancillary
and
Andean
Andersen
Anderson
Andes
andesine
andesite
andiron
Andorra
Andover
Andre
Andrea
Andrei
Andrew
Andrews
Andromache
Andromeda
Andy
anecdotal
anecdote
anemone
anent
anew
angel
Angela
Angeles
angelfish
angelic
Angelica
Angelina
Angeline
Angelo
anger
Angie
angiosperm
angle
Angles
Anglican
Anglicanism
angling
Anglo
Anglophobia
Angola
Angora
angry
angst
angstrom
anguish
angular
Angus
anharmonic
Anheuser
anhydride
anhydrite
anhydrous
ani
aniline
animadversion
animadvert
animal
animate
animism
animosity
anion
anionic
anise
aniseikonic
anisotropic
anisotropy
Anita
Ankara
ankle
Ann
Anna
annal
Annale
Annalen
annals
Annapolis
Anne
anneal
Annette
annex
Annie
annihilate
anniversary
annotate
announce
annoy
annoyance
annual
annuity
annul
annular
annuli
annulled
annulling
annulus
annum
annunciate
anode
anodic
anomalous
anomaly
anomie
anonymity
anonymous
anorexia
anorthic
anorthite
anorthosite
another
Anselm
Anselmo
ANSI
answer
ant
antacid
Antaeus
antagonism
antagonist
antagonistic
antarctic
Antarctica
Antares
ante
anteater
antebellum
antecedent
antedate
antelope
antenna
antennae
anterior
anteroom
anthem
anther
anthology
Anthony
anthracite
anthracnose
anthropogenic
anthropology
anthropomorphic
anthropomorphism
anti
antic
anticipate
anticipatory
Antietam
antigen
Antigone
antigorite
antimony
Antioch
antipasto
antipathy
antiperspirant
antiphonal
antipode
antipodean
antipodes
antiquarian
antiquary
antiquated
antique
antiquity
antisemite
antisemitic
antisemitism
antithetic
antler
Antoine
Antoinette
Anton
Antonio
Antony
antonym
Antwerp
anvil
anxiety
anxious
any
anybody
anybody'd
anyhow
anyone
anyplace
anything
anyway
anywhere
aorta
A&P
apace
apache
apart
apartheid
apathetic
apathy
apatite
ape
aperiodic
aperture
apex
aphasia
aphasic
aphelion
aphid
aphorism
Aphrodite
apices
apiece
aplomb
apocalypse
apocalyptic
Apocrypha
apocryphal
apogee
Apollo
Apollonian
apologetic
apologia
apology
apostate
apostle
apostolic
apostrophe
apothecary
apothegm
apotheosis
Appalachia
appall
appanage
apparatus
apparel
apparent
apparition
appeal
appear
appearance
appeasable
appease
appellant
appellate
append
appendage
appendices
appendix
apperception
appertain
appetite
Appian
applaud
applause
apple
Appleby
applejack
Appleton
appliance
applicable
applicant
applicate
application
applied
applique
apply
appoint
appointe
appointee
apport
apportion
apposite
apposition
appraisal
appraise
appreciable
appreciate
apprehend
apprehension
apprehensive
apprentice
apprise
approach
approbation
appropriable
appropriate
approval
approve
approximable
approximant
approximate
Apr
apricot
April
apron
apropos
APS
apse
apt
aptitude
aqua
aquarium
Aquarius
aquatic
aqueduct
aqueous
Aquila
Aquinas
AR
Arab
arabesque
Arabia
Arabic
Araby
Arachne
arachnid
arbiter
arbitrage
arbitrary
arbitrate
arboreal
arboretum
arbutus
arc
arcade
Arcadia
arcana
arcane
arccos
arccosine
arch
archae
archaic
archaism
archangel
archbishop
archdiocese
archenemy
Archer
archery
archetype
archetypical
archfool
Archibald
Archimedes
arching
archipelago
architect
architectonic
architectural
architecture
archival
archive
arcing
arclength
arcsin
arcsine
arctan
arctangent
arctic
Arcturus
Arden
ardency
ardent
arduous
are
area
areaway
areawide
arena
arenaceous
aren't
Arequipa
Ares
Argentina
argillaceous
arginine
Argive
argo
argon
Argonaut
Argonne
argot
argue
argument
argumentation
argumentative
Argus
arhat
Ariadne
Arianism
arid
Aries
arise
arisen
aristocracy
aristocrat
aristocratic
Aristotelean
Aristotelian
Aristotle
arithmetic
Arizona
ark
Arkansan
Arkansas
Arlen
Arlene
Arlington
arm
armada
armadillo
Armageddon
armament
Armata
armature
armchair
Armco
Armenia
Armenian
armful
armhole
armillaria
armistice
armload
armoire
Armonk
Armour
armpit
Armstrong
army
Arnold
aroma
aromatic
arose
around
arousal
arouse
ARPA
arpeggio
arrack
Arragon
arraign
arrange
arrangeable
array
arrear
arrest
Arrhenius
arrival
arrive
arrogant
arrogate
arrow
arrowhead
arrowroot
arroyo
arsenal
arsenate
arsenic
arsenide
arsine
arson
art
Artemis
artemisia
arterial
arteriole
arteriolosclerosis
arteriosclerosis
artery
artful
arthritis
Arthur
artichoke
article
articulate
articulatory
Artie
artifact
artifice
artificial
artillery
artisan
artistry
Arturo
artwork
arty
Aruba
arum
aryl
a's
as
asbestos
ascend
ascendant
ascension
ascent
ascertain
ascetic
asceticism
ascomycetes
ascribe
ascription
aseptic
asexual
ash
ashame
ashamed
ashen
Asher
Asheville
Ashland
Ashley
ashman
ashmen
Ashmolean
ashore
ashtray
ashy
Asia
Asiatic
aside
Asilomar
asinine
ask
askance
askew
asleep
asocial
asparagine
asparagus
aspartic
aspect
aspen
asperity
aspersion
asphalt
aspheric
asphyxiate
aspidistra
aspirant
aspirate
aspire
aspirin
asplenium
assai
assail
assailant
Assam
assassin
assassinate
assault
assay
assemblage
assemble
assent
assert
assess
assessor
asset
assiduity
assiduous
assign
assignation
assignee
assimilable
assimilate
assist
assistant
associable
associate
assonant
assort
assuage
assume
assumption
assurance
assure
Assyria
Assyriology
Astarte
astatine
aster
asteria
asterisk
asteroid
asteroidal
asthma
astigmat
astigmatic
astigmatism
ASTM
astonish
Astor
Astoria
astound
astraddle
astral
astray
astride
astringent
astrology
astronaut
astronautic
astronomer
astronomic
astronomy
astrophysical
astrophysicist
astrophysics
astute
Asuncion
asunder
asylum
asymmetry
asymptote
asymptotic
asynchronous
asynchrony
at
Atalanta
atavism
atavistic
Atchison
ate
Athabascan
atheism
atheist
Athena
Athenian
Athens
athlete
athletic
athwart
Atkins
Atkinson
Atlanta
atlantes
Atlantic
atlantic
Atlantica
Atlantis
atlas
atmosphere
atmospheric
atom
atomic
atonal
atone
atop
Atreus
atrium
atrocious
atrocity
atrophic
atrophy
Atropos
AT&T
attach
attache
attack
attain
attainder
attempt
attend
attendant
attendee
attention
attentive
attenuate
attest
attestation
attic
Attica
attire
attitude
attitudinal
attorney
attract
attribute
attribution
attributive
attrition
attune
Atwater
Atwood
atypic
Auberge
Aubrey
auburn
Auckland
auction
auctioneer
audacious
audacity
audible
audience
audio
audiotape
audiovisual
audit
audition
auditor
auditorium
auditory
Audrey
Audubon
Auerbach
Aug
Augean
augend
auger
augite
augment
augmentation
augur
august
Augusta
Augustan
Augustine
Augustus
auk
aunt
auntie
aura
aural
Aurelius
aureomycin
auric
Auriga
aurochs
aurora
Auschwitz
auspices
auspicious
austenite
austere
Austin
Australia
Australis
australite
Austria
authentic
authenticate
author
authoritarian
authoritative
autism
autistic
auto
autobiography
autoclave
autocollimate
autocorrelate
autocracy
autocrat
autocratic
autograph
automat
automata
automate
automatic
automaton
automobile
automorphic
automorphism
automotive
autonomic
autonomous
autonomy
autopsy
autosuggestible
autotransformer
autumn
autumnal
auxiliary
avail
avalanche
avarice
avaricious
Ave
avenge
Aventine
avenue
aver
average
averred
averring
averse
aversion
avert
avertive
Avery
Avesta
aviary
aviate
aviatrix
avid
avionic
Avis
Aviv
avocado
avocate
avocation
avocet
Avogadro
avoid
avoidance
Avon
avow
avowal
avuncular
await
awake
awaken
award
aware
awash
away
awe
awesome
awful
awhile
awkward
awl
awn
awoke
awry
ax
axe
axes
axial
axiology
axiom
axiomatic
axis
axisymmetric
axle
axolotl
axon
aye
Ayers
Aylesbury
AZ
azalea
Azerbaijan
azimuth
azimuthal
Aztec
Aztecan
azure
b
babbitt
babble
Babcock
babe
Babel
baboon
baby
babyhood
Babylon
Babylonian
babysat
babysit
babysitter
babysitting
baccalaureate
baccarat
Bacchus
Bach
bachelor
bacilli
bacillus
back
backboard
backbone
backdrop
backfill
backgammon
background
backhand
backlash
backlog
backorder
backpack
backplane
backplate
backscatter
backside
backspace
backstage
Explanation / Answer
/ A C program to print all anagarms together
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// structure for each word of duplicate array
struct Word
{
char* str; // to store word itself
int index; // index of the word in the original array
};
// structure to represent duplicate array.
struct DupArray
{
struct Word* array; // Array of words
int size; // Size of array
};
// Create a DupArray object that contains an array of Words
struct DupArray* createDupArray(char* str[], int size)
{
// Allocate memory for dupArray and all members of it
struct DupArray* dupArray =
(struct DupArray*) malloc( sizeof(struct DupArray) );
dupArray->size = size;
dupArray->array =
(struct Word*) malloc( dupArray->size * sizeof(struct Word) );
// One by one copy words from the given wordArray to dupArray
int i;
for (i = 0; i < size; ++i)
{
dupArray->array[i].index = i;
dupArray->array[i].str = (char*) malloc( strlen(str[i]) + 1 );
strcpy(dupArray->array[i].str, str[i] );
}
return dupArray;
}
// Compare two characters. Used in qsort() for sorting an array of
// characters (Word)
int compChar(const void* a, const void* b)
{
return *(char*)a - *(char*)b;
}
// Compare two words. Used in qsort() for sorting an array of words
int compStr(const void* a, const void* b)
{
struct Word* a1 = (struct Word *)a;
struct Word* b1 = (struct Word *)b;
return strcmp(a1->str, b1->str);
}
// Given a list of words in wordArr[],
void printAnagramsTogether(char* wordArr[], int size)
{
// Step 1: Create a copy of all words present in given wordArr.
// The copy will also have orignal indexes of words
struct DupArray* dupArray = createDupArray(wordArr, size);
// Step 2: Iterate through all words in dupArray and sort
// individual words.
int i;
for (i = 0; i < size; ++i)
qsort(dupArray->array[i].str,
strlen(dupArray->array[i].str), sizeof(char), compChar);
// Step 3: Now sort the array of words in dupArray
qsort(dupArray->array, size, sizeof(dupArray->array[0]), compStr);
// Step 4: Now all words in dupArray are together, but these
// words are changed. Use the index member of word struct to
// get the corresponding original word
for (i = 0; i < size; ++i)
printf("%s ", wordArr[dupArray->array[i].index]);
}
// Driver program to test above functions
int main()
{
char* wordArr[] = {"cat", "dog", "tac", "god", "act"};
int size = sizeof(wordArr) / sizeof(wordArr[0]);
printAnagramsTogether(wordArr, size);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.