[algogeeks] Re: check string A and B isPermutation ?
I had written.. So, using a sort the complexity really is O(2n log 2), Isn't it? Oh yeah.. That's terribly bad logic! @Gene Use radix sort to make it O(N W) where W is the bit-width of the characters in the string, hence O(N). I don't really get how a radix pass is going to help here either.. Wouldn't it just order the strings, while we really want to order the characters in the strings? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: check string A and B isPermutation ?
i think we just construct a string C that repeate string A twice, for example, string A is 'abcd', and string C is 'abcdabcd', then check whether string B is a substring of string C. by the way, the string C can be saved by utilizing string A and modular function, for example, the char at position i in string C is exactly the char at i%len(A) in string A. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: check string A and B isPermutation ?
Assuming that you cannot have any letter repeated more than 15 times. Create a struct of 26, 4 bit bitfields. This is going to take 26x4 bits or 13 bytes of memory. Use this structure to store the character count of each character of the first string. Now proceed to the second string and for each character, decrease it's corresponding character count by 1 if it is greater than 0. If it is 0 then the second string is not a permutation of the first string. At the end of processin the second string check whether each caracter count is 0. If they all are 0 then the strings are permutations of one another. Of course you can modify the algo to accomodate higher maximum character counts. In any case the time required is O(n) and space required is 26 x ceiling ( log ( maximum_individual_character_count, base=2) ) bits. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: check string A and B isPermutation ?
How about the prime number approach I mentioned above. Any comments?On 4/11/06, Dhyanesh [EMAIL PROTECTED] wrote:I also particularly dont like radix sort. Because it is kind of a hack. It is not a comparison based sort. It will work with charactersas you have here. But what if you have not two strings of characters,but two arrays of objects which you can only compare. You would not be able to apply radix sort then.-DhyaneshOn 4/11/06, Kevin [EMAIL PROTECTED] wrote: Talking about radix sorting, my experience is that many job interviewers (who are coders/developer themselvef) do not like it. Each time when I mentioned it, they usually did not get happy with it. What could be the reason? Any bad things in practical for radix sorting? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: check string A and B isPermutation ?
With the prime number approach you would need to somehow facilitate large numbers. Also, you need to store those primes which would take a lot of space, although admittedly you only need to take that space once. In addition, multiplication is a much heavier opperation than increment. BiGYaN's approach is nice but does not scale for large strings. If the strings are enourmous then an array of links to the counts with the ability to increase the number of bits in a counter on the fly might work, although that's getting complex and would take space. If space is the main consern, wouldn't some sort of radix sort work here? You could sort the bytes of each string according to one bit (say the least significant of the relevant bits), that would partition the strings into two parts. The sort could be done by starting both from left and right ends and exchanging elements that are not in the appropriate partition (left or right). Once done with the first bit, check if the partitioning position is different, if it is then A is no permitation of B and stop. Otherwise continue with the next relevant bit. This is O(N * w) where w is the number of bits need to be checked before returning FALSE or the total number of relevant bits in a character in the worst case. No additional space required. --Timak Padmanabhan Natarajan [EMAIL PROTECTED] writes: How about the prime number approach I mentioned above. Any comments? On 4/11/06, Dhyanesh [EMAIL PROTECTED] wrote: I also particularly dont like radix sort. Because it is kind of a hack. It is not a comparison based sort. It will work with characters as you have here. But what if you have not two strings of characters, but two arrays of objects which you can only compare. You would not be able to apply radix sort then. -Dhyanesh On 4/11/06, Kevin [EMAIL PROTECTED] wrote: Talking about radix sorting, my experience is that many job interviewers (who are coders/developer themselvef) do not like it. Each time when I mentioned it, they usually did not get happy with it. What could be the reason? Any bad things in practical for radix sorting? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: check string A and B isPermutation ?
[EMAIL PROTECTED] writes: So this is no better than just having an array of the counts per character, in terms of space and worse in terms of speed. :-/ Actually, what was I thinking, the radix approach would be better, spacewise. In terms of space it would require O(w) space where w is the number of bits used for the determination. The array of sums approach (what Pramod Patangay suggested earlier) requires O(K) space where K is the number of characters. Since w is logK or less, the radix approach is better. Speedwise, the array of sums would be O(2N), while the radix is O(2N*w). Both are O(N) since w is a constant relatively small, in case of huge N. [boy, I just replied to my own message for a second time :-)] --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
