New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
proposal: strings: function to check if a string contains all specified runes #63328
Comments
how common is this that it should be in the standard library? |
Thank you for filing this issue @abdullah-alaadine and welcome to the Go project. Thanks @seankhliao for the reply! @abdullah-alaadine if I may, I believe that for correctness you wanted to use an inversion of the conditions so package main
import (
"strings"
)
func containsAll(s string, wants []rune) bool {
for _, r := range wants {
if !strings.ContainsRune(s, r) {
return false
}
}
return true
}
func main() {
println(containsAll("hello world from Go!", []rune("eld")))
} but purely academically, that code above is expensive in the worst case which could become a quadratic time complexity lookup Improved implementationFor large strings or larger slices of want, you could use strings.ContainsFunc which got introduced in Go1.20 to iterate exactly once over package main
import (
"strings"
)
func containsAll(s string, wants []rune) bool {
m := make(map[rune]bool, len(wants))
// iterates over all the runes in wants exactly once: O(l)
for _, r := range wants {
m[r] = false
}
// Iterates over all the string's runes exactly once: O(k)
strings.ContainsFunc(s, func(r rune) bool {
if _, inWants := m[r]; inWants {
// Constants time lookups & insertions: O(1)
m[r] = true
}
return false // Return false to iterate over all runes in s.
})
for _, wasSeen := range m {
if !wasSeen {
return false
}
}
return true
}
func main() {
println(containsAll("hello world from Go!", []rune("elfd")))
println(containsAll("hello world from Go!", []rune("elfdz")))
} Academically my above suggestion seems cheaper but in practice for small slices, iterating over 2 slices is very fast and cheaper Proposal motivations and demand for this codeNow given that a more efficient implementation had to be scrutinized by myself and it requires more thought for larger values, perhaps that's good motivation for the standard library to take the logic away from everyone having to implement it, however we need data how much code out there has to look for all runes, how often is this pattern required, can you please compile usages of the need for this code? @rsc got a Go corpus compiled and also Sourcegraph allows you to search over public Go repositories https://sourcegraph.com/search /cc @sqs @beyang |
mm, yes I think that the real-world use cases for this function are relatively rare, for me, I needed this helper function in this LeetCode problem "316. Remove Duplicate Letters", where I want to check if a substring of the whole string contains a set of specific characters, but I can solve the problem in a simpler and more efficient way, and I don't have specific public examples to point to, but I've thought of some use cases that this helper function is useful, like if I am building a game, where users need to press specific keys a certain number of times, and the order of the input doesn't matter (which it's not usually case in games). Anyway, I'll add the updated implementation of this function to make it work as expected. (The provided one above is just to explain the purpose of it, it won't work as expected in some cases). function version 2:
The problem with this implementation is that if the developer need to check if x number of a specific rune is in the string, like function version 3:
example on using it:
|
Thank you, @odeke-em, for your notes. Yes, you are right; I missed the '!' unintentionally. I'll search to see if there are a decent number of use cases for this helper function to determine whether it's worth adding to the standard library or not. |
Gotcha and thank you for giving me the context for your need @abdullah-alaadine! I just looked at your problem and I believe you can definitely solve it in much simpler, more efficient and faster ways without having to use a map, you can just use a slice of 26 booleans values as an index, given the constraints:
so https://go.dev/play/p/ecMWraalU5J package main
import "fmt"
func dedupLettersAndLexicographicOrder(s string) string {
// Constraint, lower case English letters in s.
// Output: Deduplicated letters in lexicographic order.
index := make([]bool, 26)
for _, r := range s {
if i := r - 'a'; index[i] == false {
index[i] = true
}
}
// Finally return the result:
res := make([]rune, 0, len(index))
for i, ok := range index {
if ok {
res = append(res, rune(i+'a'))
}
}
return string(res)
}
func main() {
rubric := map[string]string{
"aaaaaaabdeeeecfff": "abcdef",
"bbbefffghaaaaaaa": "abefgh",
}
for input, want := range rubric {
got := dedupLettersAndLexicographicOrder(input)
if got != want {
fmt.Printf("%q =>\n\tGot: %q\n\tWant: %q", input, got, want)
}
}
} I think that once you get good data on this then the proposal can proceed. |
Thanks for sharing your solution. @odeke-em
Example 1 is clear, but in example 2, as you can see, the output is |
after spending sometime on searching for real-world use cases for such function, where the developer has to use this function, I didn't find any real-world scenario for it, so I think it's better not adding it to the standard library. I'd like to hear back from you about your take on it, and thanks! |
I think you're probably right; I don't think I've ever needed this function except when solving word puzzles. |
Use Case
Sometimes I encounter scenarios where I need to check if a given string contains all of a specific set of runes, such as vowels ('a', 'e', 'i', 'o', 'u'). Currently, I have to iterate through the string and runes manually.
Proposal
I propose adding a function to the strings package that can efficiently check if a string contains all of the specified runes. For example:
- Note that I didn't prefixed ContainsRune function with 'strings' which is the name of the package, because this function is intended to be in the strings package
- The implementation provided above is a basic example for illustration purposes.The actual implementation can be optimized for better performance and efficiency.
This function would greatly simplify such checks and improve code readability.
usage example:
The text was updated successfully, but these errors were encountered: