Question

given a string two strings say s1 and s2....write an algorithm to check if s2 is a permutation of s1
vcf is a permutation of cfv...

Answer 1

Hello here a small program to solve this in C :
**************************************************************
#include<stdio.h>
#include<string.h> //So I can work with strings.

int main(int argc, char** argv){ //I will give s1 and s2 as parameters
//from the command line
if(strlen(argv[1]) != strlen(argv[2])){ //I tested if s1 has the same length as s2
// if not that means they aren't permutation.
printf("%s is not a permutation of %s", argv[2], argv[1]);
}else{
int i=0; //I start with 0 because in strings we start with 0 not 1.
int j=strlen(argv[2])-1; //I started with 0, so I make it -1
while((i<=strlen(argv[1])-1) && j>=0){
//Here my principe is to test the first letter of s1 with the last of s2
// then the second of s1 with the last-1 of s2, and so on...
if(argv[1][i] != argv[2][j]) { // If 2 letters aren't the same
// That means it's not a permutation.
printf("%s is not a permutation of %s", argv[2], argv[1],i);
break;
}else{
i++;
j--;
}
}
//If all the letters are equal, means it's a permutation.
printf("%s is a permutation of %s", argv[2], argv[1]);
}
}
****************************************************************

To run this program you need to compile it, I'm using Dev-C++, so I will assume the you named your program 'avinash' and you saved it in the desktop, so after you compile you will find a file in your desktop with the name 'avinash.exe':

Here run the command line 'cmd' then go to your desktop and type :
avinash fcv vcf
and hit enter , you will get the result.

Good luck. ktobah.

Answer 2

it's like the permutations of vcf are vfc,fcv,cvf,....u have 6 of them...
what i thot was sort the strings and compare those strings... i was wondering if ther's a faster method

Answer 3

Well I think the permutation mean to divide the sting into 2, it's this is the case then every word has just 1 permutation, and if this the case too so you NEED to check all the two strings.
maybe I'm wrong, I dunno.

Answer 4

you can use next permutation in C++

Answer 5

sorting the strings i a bad idea, if you want to now if s1 contain the exact same characters with s2 you can do what @ktobah said.If you want to see if one string is a permutation of another then you might have to create a function that computes every possible permutation of one string and compares it with the other string

Answer 6

actually this is not true, if one string contains the exact same characters with another string then it's definately one of the N! permutations of it.So you just have to do what @ktobah said in linear time.

Answer 7

But if a word has many possible permutations then we can consider my program wrong, because it solves the problem just partially.

Answer 8

um wat's divinding string in to two?

Answer 9

if it's like splitting the string till u get substrings of length 1.....then splitting takes a O(nlogn)

nd i know that sorting is a bad idea coz it takes a lot of time...but it does work r8?

thank you :)

Answer 10

@ktobah all the strings with length > 1 have many possible permutations.But your algorithm is correct.Consider string A=a1,a2,a3,...,an where ai is a character.And a second string B=b1,b2,b3,...,bn.We define permutation of a string, any possible rearrangment of the characters so that there is one or more i's so that ai!=a'i.Let A'=ai,ai+1,ai+2,...an, and B'=ai,ai+1,ai+2,...,an.If for every i in string A there is a j in string B so that Ai=Bj then there is a possible permutation of A so that A=B.

Answer 11

so how do u get an algo of complexity O(N)

Answer 12

i am not sure if an o(N) algorithm is possible

Answer 13

yea.....the best i could think of is O(n*n)
i figured out two ways
sort the arrays and compare them
or
check if a given character is in the string.... i could think of a modification to this like removing the compared item each time..... this reduces the number comparisions after each run

Answer 14

That's what i figured out too.But there is an O(nlogn) solution which is quite good...

Answer 15

like merge sort?

Answer 16

yeah..

Answer 17

ok....like sorting using merge sort right,,,,?

Answer 18

yeah...

Answer 19

ok fine....
thank you @ktobah @infinity_

Answer 20

There is an O(N) algorithm :P

Answer 21

o.O

Answer 22

You can count each letter appearance and compare it with the letter appearance in the other string.

Answer 23

*.*
wow

Answer 24

why do i always miss things -.-

Answer 25

I almost missed it too :P

Answer 26

gosh but it is really awsome......

Answer 27

thanks again @infinity_ nd @ktobah

Answer 28

hey i got another question...well i have a solutin for this but i wonder "is there a better one!! :-/"

given a character array say "there is always a better algorithm"
write code for a function that changes it to "algorithm better a always is there"
this should be space efficient.

what i did was reverse the ntire string and later reverse every word ...
i wonder if ther's a better method

Answer 29

the complexity of your algorithm is O(N).Is there a faster method? No because you have to read the whole string before doing anything which, by itself, has a complexity of O(N).

Answer 30

ok :)