Блог пользователя runtime_error

question about some string problems
Автор runtime_error, 11 лет назад, По-английски

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??

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Empty string is string too?

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    yes

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        thanks,i understood now.

        → Ответить
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить