runtime_error's blog

question about some string problems
By runtime_error, 11 years ago, In English

I see in many string problems like this: Find how many string there is of given length n, consisting only of the characters: 'a', 'b',and "c", and do not contain the substring "ab". In this problem answer of simple tests : n=0 answer=1 why answer is 1??why??

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Empty string is string too?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That question from BekzhanKassenov answers your question. Empty string neither has any invalid character(characters except 'a', 'b', 'c') nor has "ab" as substring. So an empty string is a valid string for this question.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks,i understood now.

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Be careful of 'empty set answers', and also in other problems, e.g.count how many sets of vertices(or edges)in a tree that satisfy some certain constraints. In many cases empty set will be a correct answer.

          → Reply