Y’all wouldn’t happen to have some handy mental model for remembering how to iterate through input without being an idiot about it, would you?

Referring to problems like having to get all possible substrings from a given string, etc.

Wishful thinking on my part, probably, but I figure it doesn’t hurt to ask. <3

  • 1
    What do you mean by iterating input? You need to read all input to memory to produce all substrings.
  • 2
    @AmbientTea Ah, sorry, I need to learn to communicate to the voices outside of my head better.

    I mean, in the case of needing to find all the possible substrings of a string, you can't just loop over the input in one pass because you need at least two pointers at any one time (for the start and end of the substring) and both need to move.

    So for getting all of the anagrams of a string, you might have an outer loop starting at 0 and ending before the end of the array and an inner loop from the index of the outer loop + 1 to the end of the array.

    But sometimes you're in a situation where it calls for the inner loop of a nested loop function to end at the index of the outer loop, or to begin at the opposite end of the input than the outer loop.

    Was just wondering if any of you just have a cool way of remembering how to structure nested loops and how to determine if you even need a nested loop in the first place.
  • 1
    Well you determine it the way you did. You need two pointers so there's gonna be two loops.

    for tips, a common approach is to always have the left/lower bound inclusive and the right/upper bound exclusive, so you loop through [x, y). If you don't need to it's best to have all loops go in the same direction too and use the same comparator, so no mixing < > <= etc. Best if your language supports ranges instead of C for ofc.

    Dunno if that's helpful, i don't have many opportunities to write loops.
  • 0
    Isn't it, like, a trivial task?

    First iterator goes from start to end one time. Second iterator goes from current position of the first to end after each step of the first iterator.

    Not a very efficient stuff as it is quadratic relative to the length of the array.
  • 1
    @AmyShackles with anagrams I assume you mean permutations?

    I would use a recursive method with a loop.

    The method loops over all chars in the current input and for each makes a call to it self with the rest of the chars.

    And for each char you then prepend it to every result from the call.

    Aggregate all results from all calls in the loop and return a list (possibly removing any duplicates to lessen memory consumption)

    When the last method returns you have all.

    Might not be the fastest or most efficient but it should work.
  • 1
    @Voxera Sorry, what I meant was... I spent a good deal of time trying to figure out how to solve this problem and went through a lot of trial and error before I figured it out: https://hackerrank.com/challenges/...

    And I’ve realized that I generally have trouble working out the solutions to problems that require iterating through input through multiple passes in general. 2D matrices are the subject of many a nightmare.

    So I was really more wondering if there’s some stupid trick to it that I’ve somehow missed.

    And yes, @iiii, you’re right. It _is_ probably a trivial task. Believe me when I say I felt like an idiot asking in the first place.
  • 2
    @AmyShackles ok:)

    I usually try to solve a very simple version using pen and paper to get an understanding of the problem.

    Then use code to scale up to whatever I need.

    But mostly I think it is a matter of doing it often enough to learn a number of methods that you can easily use to break a problem down.

    I have used codewars to get fun challenges to train on.
  • 0
    @AmyShackles that's a curious task. Overall it is not as trivial as just taking all the substrings.
  • 0
    I see at least one trick: if there are two short anagrammatic strings then substrings which include them and a substring between those two are anagrammatic as well.

    For example "ifai". "i" and "i" are anagrammatic, so if you include the part "fa" in-between, you'll get another pair "ifa" and "fai"
Add Comment