6
\$\begingroup\$

I'm trying to improve my code and algorithm to find out the longest word from a dictionary occurring as the sub-sequence in the given string.

Example : For example, given the input of S = "abppplee" and D = {"able", "ale", "apple", "bale", "kangaroo"} the correct output would be "apple".

Currently my algorithm compares each character of the dictionary-word with the given-word and advances to next char in dictionary-word on finding a match and so on till either the dictionary-word is iterated over completely(which means the word is a valid sub-sequence) or the given word is iterated over completely(which means not a valid string).

Being a beginner to c++ and algorithms in general, my methods and logic could be further improved. So kindly suggest if any improvements in the algorithm or code which can improve the performance. Thanks.

#include <iostream>
#include <string>
#include <tuple>
#include <vector>

class StringManipulater {
  public:
  StringManipulater(const std::string& p) : given_string_{p} {}
  std::string given_string_;
  std::tuple<std::string, typename std::string::size_type> current_longest_ = {
      "", 0};

  const std::string&& FindLongestSubSeq(const std::vector<std::string>& dict)
  {
    // flag determines whether current word is present in given_string input
    bool flag;

    // iterate through each of the dict-words
    for (const std::string& word : dict) {
      flag = false;
      auto word_len = word.size();

      // fair optimization : only consider current word if its
      // length is greater than previous one
      if (word_len > std::get<1>(this->current_longest_)) {
        // iterate through the letters in both given string and current word
        // to be compared
        for (typename std::string::size_type i = 0, j = 0; j < word_len; ++i) {
          // no need to go further checking if we have iterated over given
          // string
          if (i == this->given_string_.size()) break;

          // compare each letter of both words
          if (word[j] == given_string_[i]) {
            flag = true;
            // advance to next charcter in the dictionary word
            ++j;
          }
          else {
            // if the char couldn't be found
            flag = false;
          }
        }  // end of comparison loop
        if (flag) {
          std::get<0>(this->current_longest_) = word;
          std::get<1>(this->current_longest_) = word_len;
        }
      }  // top if
    }    // end of iteration of dictionary words
    return std::move(std::get<0>(this->current_longest_));
  }
};

int main()
{
  StringManipulater s_manip{"abppplee"};
  std::cout << "Longest subsequence = "
            << s_manip.FindLongestSubSeq(
                   {"able", "ale", "apple", "bale", "kangaroo"})
            << "\n";
  return 0;
}
\$\endgroup\$
7
\$\begingroup\$

You know, if you want to improve performance, the first thing to do is get a high-level overview of what your code does to achieve its aim. Currently, you do this:

  1. Iterate over all words in D.
    1. Iterate over the whole string S trying to prove it a sub-sequence.

That's trivially proven to be an \$O(\#D * \#S)\$ algorithm.

You can do better, by using the proper data structure:

  1. Build a prefix-tree from the words, noting the longest word which can be found from there.
  2. Iterate over the string.
    1. Continue if the current character doesn't fit.
    2. Update the best found if it is a terminal node.
    3. recurse with the sub-tree.

Regarding your code:

  1. Your use of a class is completely unmotivated. There are no invariants to protect, as evidenced by you marking it all public, and you only create it to call one single function anyway. Just make it a free function. Ok, if you change the algorithm, you might want to break it up it into building the trie, using a pre-computed trie, and putting it all together.

  2. auto would allow you to always have the proper type, without cluttering your code with long and obscure names. Read "Almost Always Auto".

  3. I'm not sure why you use a std::tuple. Maybe for obfuscation? If so, I confirm you are on the right way.

  4. Always define variables in the smallest scope possible, unless there are significant advantages (most likely in performance) for a slightly longer lifetime.

  5. return 0; is implicit for main().

\$\endgroup\$
2
  • \$\begingroup\$ This helps! Several questions though -> 1) Did you know by heart the time complexity of my algorithm or did you compute it somehow? I wanted to properly learn the computation of time/space complexities. Any recommendations for learning materials/courses? -> 2) I did not understand "defining variables in smallest scope" part. Did you mean, like declaration of flag could have been inside the for loop rather than outside? -> 3) I used the tuple to hold the longest string and it's length(which i use for comparison). Are tuples or usage of other containers like so not a good practice? \$\endgroup\$ – Yedhin Jan 20 '19 at 3:08
  • \$\begingroup\$ @Yedhin 1. Computed: At worst, none of the words are found. Then just look at the loops. 2. current_longest should obviously not be a member, but a local of the function. And yes to flag. 3. Using tuples iwhen you need a bag is no problem, and can help composability. That's not the case though, there was no downside to having two independent symbols at all, so being more descriptive and convenient is far better. \$\endgroup\$ – Deduplicator Jan 20 '19 at 11:01
4
\$\begingroup\$
  • C++ is not Java. You don't need to spell out this->.

  • Flat is better than nested. Consider

    if (word_len <= std::get<1>(current_longest_)) {
        continue;
    }
    // Follow with the business logic unindented
    
  • I'd prefer to alias typename std::string::size_type as

    using size_type = typename std::string::size_type;
    

    or, even better, use iterators.

  • The inner loop can be streamlined. When we see bool flag; the instinct tells to get rid of it. Upon the loop termination the same information is available as j == word_len (or word_it == word_end() in the iterator version). We just need to lift j (or word_it) out of the loop.

    Another problem with the inner loop is that it manages two indices in a not-so-obvious way. A cleaner approach is to let the loop manage just the word, and another (innermost) loop to search through the given string. Consider

    auto str_it = given_string.begin();
    auto word_it = word.begin();
    while (word_it != word.end()) {
        while (str_it != given_string.end() && *str_it != *word_it) {
            ++str_it;
        }
        if (str_it == given_string.end()) {
            break;
        }
        ++word_it;
    }
    

    Now we notice that the innermost loop does the same job as std::find_first. Use it:

    while (word_it != word.end()) {
        if ((str_it = std::find_first(str_it, str.end(), *word_it)) == str_end()) {
            break;
        }
        ++word_it;
    }
    
  • I also recommend to factor a body of the for (const std::string& word : dict) loop out into a function:

    const std::string&& FindLongestSubSeq(const std::vector<std::string>& dict)
    {
        std::tuple<std::string, typename std::string::size_type> current_longest_
            = { "", 0 };
        for (const std::string& word : dict) {
            if (word_len <= std::get<1>(current_longest_)) {
                continue;
            }
    
            if (is_subsequence(given_string, word)) {
                std::get<0>(this->current_longest_) = word;
                std::get<1>(this->current_longest_) = word.size();
            }
        return std::move(std::get<0>(this->current_longest_));
    }
    
  • Finally, I recommend to get rid of the class StringManipulater altogether, and implement everything as free functions. The class does not add any value (an C++ is not Java).

\$\endgroup\$
1
  • \$\begingroup\$ This helps a lot. Several questions though -> 1)Should iterators be preferred over usual for(i=0;...;i<size) or for(const int val&: container) loops for iterating containers? If yes, why? 2) I started using OOP in everything after hearing a talk by Bjarne Stroustrup. Are there any caveats/overheads by using a Class in every program? \$\endgroup\$ – Yedhin Jan 20 '19 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.