Ankur Luthra wrote:
1)What would be the best approach for the problem.
2) What would be the final DataStructure representing groups and Similar Strings.
3)What should be the approach for this problem.
Jeff Verdegan wrote:Another approach--that may or may not work for you--is to use a BitSet for each string and turn on the bits corresponding to the letters that are present in that String. If two BitSets have the same bits turned on, then the corresponding Strings contain the same letters.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Ankur Luthra wrote:I was able to do it in following way. Any comments to improve performance if the Array size increases?
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:
Jeff Verdegan wrote:Another approach--that may or may not work for you--is to use a BitSet for each string and turn on the bits corresponding to the letters that are present in that String. If two BitSets have the same bits turned on, then the corresponding Strings contain the same letters.
I fear I see a fatal flaw in that approach, kemosabe: wouldn't "AB" and "AAB" produce the same BitSet?
Winston
Ankur Luthra wrote:I was able to do it in following way.Any comments to improve performance if the Array size increases?
Jeff Verdegan wrote:
Ankur Luthra wrote:I was able to do it in following way.Any comments to improve performance if the Array size increases?
Not regarding performance in particular, just general comments:
1. Your ModifiedString class should not have setters. Just take the single, unsorted String as a constructor arg, and set the original and sorted variables right there.
2. It looks like there's way too much going on there. An array, and 3 Lists?
3. Don't use get(i) for iteration. Use an Iterator, whether explicit, or implied via foreach loop.
4. Two of your ArrayLists are unparameterized. You should use generics there.
5. Unless you know your variable specifically needs to be an ArrayList, just declare it as List rather than ArrayList.
Well, I notice you've defined a HashSet, but don't appear to use it. What about a HashSet of sorted strings?
Jeff Verdegan wrote:Part of what I meant when I told the OP, "I leave it to you to consider the relative merits and demerits of these approaches in the context of your requirements,"
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Ankur Luthra wrote: Can you please tell me where can I fit in HashSet in this.Are you talking about the final Data Structure i.e. finalList in my case or taking making al HashSet?
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:
Jeff Verdegan wrote:Part of what I meant when I told the OP, "I leave it to you to consider the relative merits and demerits of these approaches in the context of your requirements,"
Oh, OK. My profuse apologies.
Winston
Thank you my well lotioned goddess! Here, have my favorite tiny ad!
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
|