English subtitles

← Palindromes Solution - Intro to Computer Science

Get Embed Code
2 Languages

Showing Revision 7 created 07/09/2017 by Dejan Trajkovic.

  1. So here's a way to define is_palindrome. So we're taking
  2. a single string as an output, I will call it s,
  3. and we're first going to test the base case. So the
  4. base case was to see if the string is empty, we
  5. should return true right away. So we can do that
  6. with an if. We are going to check if s is equal
  7. to the empty string, and if it is, we return true,
  8. that's our base case. For the else, we have the recursive
  9. of case so now we need to do the test of the first and the last characters to
  10. see if they match. And we can do that
  11. using the string indexing operators, as 0 gets us
  12. the first character, s negative 1 gets us the
  13. last character. If they match, then we need to
  14. check the rest of the string. If they didn't
  15. match and let's finish the didn't match case first.
  16. So if they didn't match then we know it is
  17. a palindrome, because we found a place where the first and
  18. the last character did not match, so it should return
  19. false right away. If they did match, well then we have
  20. the harder problem. We need to do the recursive call
  21. to check all the other letters in the strings still form
  22. a palindrome. So this was our starting string. It had
  23. all these characters in it. We checked that this one matches
  24. this one, so now what we need to do is take the rest of the string and check
  25. if this is a palindrome. So that'll be a
  26. recursive call, so we're going to return the result, of calling
  27. is_palindrome. But instead of passing in s, what we
  28. want to do is pass in the string starting from
  29. position 1 of s, so removing the first character,
  30. and ending at position negative 1, removing the last character.
  31. And remember with our indexing, the last value here is
  32. not included. So by having the last index as negative
  33. 1, that removes the final letter of the string. So
  34. the first thing to test is the base case. So
  35. we'll pass in the empty string. And the empty string
  36. is a palindrome, so it should give us the result
  37. true, which it does. Let's try the single letter string,
  38. a, that's also a palindrome. It's the same backwards and forwards.
  39. And so we also get the value true, if we try say string ab, which is not a
  40. palindrome. We get false. As a longer test, if we
  41. try a level, we should get true. Which we do. And, let's try
  42. one of the most famous palindromes, amanaplanacanalpanama.
  43. And we should get True which we do.