I have a string statistics
. I need to find the unique or non repeating characters a,c
. I found a solution. But it need to use three for loops. How we can find in a easy solution which is less time consumption.
List<String> list=[];
List<String> newList=[];
//Loop one
for(int i=0; i<name.length;i ){
list.add(name[i]);
}
print(list);
newList =list.toSet().toList();
//Loop two
for(int j=0;j<list.length;j ){
//Loop three
for(int k=j 1;k<list.length;k ){
if(list[j]==list[k]){
newList.remove(list[j]);
}
}
}
print(newList);
CodePudding user response:
You can run just one for loop with the listAsASet and to check if the first index of a character is exactly the same with the last index of the same character.
See the example below:
void main() {
String sampleString = 'asdasfgalfnvcanalsdkalkcmaslksavnajskhauroewu982138954fndslkjanca135faca31asdcgdsa';
var sampleStringAsList = sampleString.split('');
var sampleStringAsSet = sampleStringAsList.toSet();
var uniqueCharactersList = [];
for(var character in sampleStringAsSet){
if(sampleStringAsList.indexOf(character) == sampleStringAsList.lastIndexOf(character)){
uniqueCharactersList.add(character);
}
}
print(uniqueCharactersList);
}
I am not sure if the split method run an extra for loop in the background though.
CodePudding user response:
You can also use the String object methods to shorten your code, for example the method indexOf finds the first match of the string that you pass to it, then the same indexOf has an option to find an index wherever you want it to start in the string, so you can first find the word "e" in "New York" and then do another search from the first match of the index 'e', then if the result is -1, is because is unique.
const string = 'New York';
final firstIndex = string.indexOf('e'); // prints the index of 'e'
final unique = string.indexOf('e', firstIndex); // prints if 'e' appears again after first match, if it prints -1 is unique, if gives an index is not unique
More information in: https://api.dart.dev/stable/2.16.1/dart-core/String/indexOf.html
CodePudding user response:
Your approach is slow because you have to constantly iterate over the input string to determine if a character exists elsewhere in the string. If you want lookups to be fast, you should be using a Map
or a Set
.
- Create a
Map
that maps individual characters to a count. - For each character in your string, increment its count in the
Map
(or initialize its count to 1 if it's not yet present in theMap
). - Iterate over the
Map
and retrieve all characters that have a count of 1.
This approach will be O(n) WRT the length of the string instead of your current O(n^3) approach (the two nested loops each contribute a multiplicative factor of n, and newList.remove()
adds another hidden factor of n).
void main() {
var s = 'statistics';
var charCodeCounts = <String, int>{};
for (var i = 0; i < s.length; i = 1) {
charCodeCounts[s[i]] = (charCodeCounts[s[i]] ?? 0) 1;
}
var uniqueCharCodes = <String>[
for (var entry in charCodeCounts.entries)
if (entry.value == 1) entry.key,
];
print(uniqueCharCodes); // Prints: [a, c]
}