forked from rsokl/Learning_Python
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathPalindrome.html
More file actions
327 lines (207 loc) · 17.1 KB
/
Copy pathPalindrome.html
File metadata and controls
327 lines (207 loc) · 17.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
<meta charset="utf-8">
<meta content="Topic: Palindrome Exercise, Difficulty: Easy, Category: Practice Problem" name="description" />
<meta content="string, palindrome, practice problem" name="keywords" />
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Is Palindrome — Python Like You Mean It</title>
<script type="text/javascript" src="../../_static/js/modernizr.min.js"></script>
<script type="text/javascript" id="documentation_options" data-url_root="../../" src="../../_static/documentation_options.js"></script>
<script src="../../_static/jquery.js"></script>
<script src="../../_static/underscore.js"></script>
<script src="../../_static/doctools.js"></script>
<script src="../../_static/language_data.js"></script>
<script src="https://www.googletagmanager.com/gtag/js?id=UA-115029372-1"></script>
<script src="../../_static/gtag.js"></script>
<script crossorigin="anonymous" integrity="sha256-Ae2Vz/4ePdIu6ZyI/5ZGsYnb+m0JlOmKPjt6XZ9JJkA=" src="https://cdnjs.cloudflare.com/ajax/libs/require.js/2.3.4/require.min.js"></script>
<script async="async" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script type="text/x-mathjax-config">MathJax.Hub.Config({"tex2jax": {"inlineMath": [["$", "$"], ["\\(", "\\)"]], "processEscapes": true, "ignoreClass": "document", "processClass": "math|output_area"}})</script>
<script type="text/javascript" src="../../_static/js/theme.js"></script>
<link rel="stylesheet" href="../../_static/css/theme.css" type="text/css" />
<link rel="stylesheet" href="../../_static/pygments.css" type="text/css" />
<link rel="stylesheet" href="../../_static/my_theme.css" type="text/css" />
<link rel="index" title="Index" href="../../genindex.html" />
<link rel="search" title="Search" href="../../search.html" />
<link rel="next" title="Within Margin Percentage" href="MarginPercentage.html" />
<link rel="prev" title="Merging Two Dictionaries" href="MergeMaxDicts.html" />
</head>
<body class="wy-body-for-nav">
<div class="wy-grid-for-nav">
<nav data-toggle="wy-nav-shift" class="wy-nav-side">
<div class="wy-side-scroll">
<div class="wy-side-nav-search" >
<a href="../../index.html" class="icon icon-home"> Python Like You Mean It
</a>
<div class="version">
1.4
</div>
<div role="search">
<form id="rtd-search-form" class="wy-form" action="../../search.html" method="get">
<input type="text" name="q" placeholder="Search docs" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
</div>
</div>
<div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
<p class="caption"><span class="caption-text">Table of Contents:</span></p>
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="../../intro.html">Python Like You Mean It</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../module_1.html">Module 1: Getting Started with Python</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../module_2.html">Module 2: The Essentials of Python</a></li>
<li class="toctree-l1 current"><a class="reference internal" href="../../module_2_problems.html">Module 2: Problems</a><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="MergeMaxDicts.html">Merging Two Dictionaries</a></li>
<li class="toctree-l2 current"><a class="current reference internal" href="#">Is Palindrome</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#Tips">Tips</a></li>
<li class="toctree-l3"><a class="reference internal" href="#Solution">Solution</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="MarginPercentage.html">Within Margin Percentage</a></li>
<li class="toctree-l2"><a class="reference internal" href="DifferenceFanout.html">Difference Fanout</a></li>
<li class="toctree-l2"><a class="reference internal" href="EncodeAsString.html">Encode as String</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="../../module_3.html">Module 3: The Essentials of NumPy</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../module_3_problems.html">Module 3: Problems</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../module_4.html">Module 4: Object Oriented Programming</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../module_5.html">Module 5: Odds and Ends</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../changes.html">Changelog</a></li>
</ul>
</div>
</div>
</nav>
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">
<nav class="wy-nav-top" aria-label="top navigation">
<i data-toggle="wy-nav-top" class="fa fa-bars"></i>
<a href="../../index.html">Python Like You Mean It</a>
</nav>
<div class="wy-nav-content">
<div class="rst-content">
<div role="navigation" aria-label="breadcrumbs navigation">
<ul class="wy-breadcrumbs">
<li><a href="../../index.html">Docs</a> »</li>
<li><a href="../../module_2_problems.html">Module 2: Problems</a> »</li>
<li>Is Palindrome</li>
<li class="wy-breadcrumbs-aside">
<a href="../../_sources/Module2_EssentialsOfPython/Problems/Palindrome.md.txt" rel="nofollow"> View page source</a>
</li>
</ul>
<hr/>
</div>
<div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
<div itemprop="articleBody">
<style>
/* CSS overrides for sphinx_rtd_theme */
/* 24px margin */
.nbinput.nblast.container,
.nboutput.nblast.container {
margin-bottom: 19px; /* padding has already 5px */
}
/* ... except between code cells! */
.nblast.container + .nbinput.container {
margin-top: -19px;
}
.admonition > p:before {
margin-right: 4px; /* make room for the exclamation icon */
}
/* Fix math alignment, see https://github.com/rtfd/sphinx_rtd_theme/pull/686 */
.math {
text-align: unset;
}
</style>
<div class="section" id="Is-Palindrome">
<h1>Is Palindrome<a class="headerlink" href="#Is-Palindrome" title="Permalink to this headline">¶</a></h1>
<blockquote>
<div><p>A palindrome is a string that reads the same from left to right and from right to left. Strings like <code class="docutils literal notranslate"><span class="pre">racecar</span></code> and <code class="docutils literal notranslate"><span class="pre">Live</span> <span class="pre">on</span> <span class="pre">time,</span> <span class="pre">emit</span> <span class="pre">no</span> <span class="pre">evil</span></code> are palindromes. Notice that only valid alphanumeric characters are accounted for and that palindromes are not case-sensitive. Given a string, return whether or not it is a palindrome.</p>
</div></blockquote>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># example behavior</span>
<span class="o">>>></span> <span class="n">is_palindrome</span><span class="p">(</span><span class="s2">"Step on no pets!"</span><span class="p">)</span>
<span class="kc">True</span>
<span class="o">>>></span> <span class="n">is_palindrome</span><span class="p">(</span><span class="s2">"'Tis not a palindrome"</span><span class="p">)</span>
<span class="kc">False</span>
<span class="o">>>></span> <span class="n">is_palindrome</span><span class="p">(</span><span class="s2">"Hi, I am Mai Ih"</span><span class="p">)</span>
<span class="kc">True</span>
</pre></div>
</div>
<div class="section" id="Tips">
<h2>Tips<a class="headerlink" href="#Tips" title="Permalink to this headline">¶</a></h2>
<p><a class="reference external" href="https://docs.python.org/3/library/stdtypes.html#str.isalnum">str.isalnum</a> returns whether or not a string has purely alphanumeric characters (it works for single-character strings too).</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="s2">"I love Python"</span><span class="o">.</span><span class="n">isalnum</span><span class="p">()</span>
<span class="go">False</span>
<span class="gp">>>> </span><span class="s2">"IlovePython"</span><span class="o">.</span><span class="n">isalnum</span><span class="p">()</span>
<span class="go">True</span>
</pre></div>
</div>
<p>Consider using this along with <code class="docutils literal notranslate"><span class="pre">str.lower</span></code> to filter out ignored characters and to normalize all of the character casing in the string before assessing whether or not it is a palindrome.</p>
</div>
<div class="section" id="Solution">
<h2>Solution<a class="headerlink" href="#Solution" title="Permalink to this headline">¶</a></h2>
<p>The simplest solution to this problem is the following, where we make use of the <code class="docutils literal notranslate"><span class="pre">str.join</span></code> function as well as slicing with a negative step:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">is_palindrome</span><span class="p">(</span><span class="n">input_str</span><span class="p">):</span>
<span class="sd">""" Given a string, determine if it is a palindrome.</span>
<span class="sd"> Whitespaces, character-casing, and non-alphanumeric</span>
<span class="sd"> characters are all ignored.</span>
<span class="sd"> Parameters</span>
<span class="sd"> ----------</span>
<span class="sd"> s: str</span>
<span class="sd"> Input string</span>
<span class="sd"> Returns</span>
<span class="sd"> -------</span>
<span class="sd"> bool</span>
<span class="sd"> """</span>
<span class="n">filtered_str</span> <span class="o">=</span> <span class="s2">""</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="n">c</span><span class="o">.</span><span class="n">lower</span><span class="p">()</span> <span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="n">input_str</span> <span class="k">if</span> <span class="n">c</span><span class="o">.</span><span class="n">isalnum</span><span class="p">())</span>
<span class="k">return</span> <span class="n">filtered_str</span> <span class="o">==</span> <span class="n">filtered_str</span><span class="p">[::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span>
</pre></div>
</div>
<p>See that <code class="docutils literal notranslate"><span class="pre">(c.lower()</span> <span class="pre">for</span> <span class="pre">c</span> <span class="pre">in</span> <span class="pre">input_str</span> <span class="pre">if</span> <span class="pre">c.isalnum())</span></code> has the form of a <a class="reference external" href="https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Generators_and_Comprehensions.html#Creating-your-own-generator:-generator-comprehensions">filtering generator comprehension</a>. Thus,</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="s2">""</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="n">c</span><span class="o">.</span><span class="n">lower</span><span class="p">()</span> <span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="n">input_str</span> <span class="k">if</span> <span class="n">c</span><span class="o">.</span><span class="n">isalnum</span><span class="p">())</span>
</pre></div>
</div>
<p>is equivalent to the long-form code:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">filtered_str</span> <span class="o">=</span> <span class="s2">""</span>
<span class="k">for</span> <span class="n">char</span> <span class="ow">in</span> <span class="n">input_str</span><span class="p">:</span>
<span class="k">if</span> <span class="n">char</span><span class="o">.</span><span class="n">isalnum</span><span class="p">():</span>
<span class="n">filtered_str</span> <span class="o">+=</span> <span class="n">char</span><span class="o">.</span><span class="n">lower</span><span class="p">()</span>
</pre></div>
</div>
<p>The generator comprehension expression is not only more concise and readable, but its use of <code class="docutils literal notranslate"><span class="pre">str.join</span></code> also makes it a more efficient means for constructing a new list. Each call to <code class="docutils literal notranslate"><span class="pre">filtered_str</span> <span class="pre">+=</span> <span class="pre">c.lower()</span></code> in the long-form code creates a new string in memory, whereas <code class="docutils literal notranslate"><span class="pre">str.join</span></code> forms a single string as it consumes the input iterable.</p>
<p>Next, <a class="reference external" href="https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/SequenceTypes.html#Slicing">recall that</a> <code class="docutils literal notranslate"><span class="pre">seq[::-1]</span></code> slices a sequence with a step of -1, which produces the sequence in <em>reverse order</em>. Thus <code class="docutils literal notranslate"><span class="pre">filtered_str</span> <span class="pre">==</span> <span class="pre">filtered_str[::-1]</span></code> allows us to compare the first character in <code class="docutils literal notranslate"><span class="pre">filtered_str</span></code> with the last and so on. This is equivalent to:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">is_equal</span> <span class="o">=</span> <span class="kc">True</span>
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">filtered_str</span><span class="p">)</span><span class="o">//</span><span class="mi">2</span><span class="p">):</span> <span class="c1"># recall: 5//2 -> 2, 6//2 -> 3</span>
<span class="k">if</span> <span class="n">filtered_str</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">!=</span> <span class="n">filtered_str</span><span class="p">[</span><span class="o">-</span><span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">)]:</span>
<span class="n">is_equal</span> <span class="o">=</span> <span class="kc">False</span>
<span class="k">break</span>
</pre></div>
</div>
<p>The only downside to using slicing to perform this comparison is that it requires that a copy of <code class="docutils literal notranslate"><span class="pre">filtered_str</span></code> be created, whereas using the explicit for-loop does not.</p>
<p>We must note that the performance differences pointed out here should only concern us if <code class="docutils literal notranslate"><span class="pre">is_palindrome</span></code> is potentially a performance bottleneck for our code. Although we want the reader to develop an intuition for writing efficient Python code, we discourage mangling code for the sake of premature optimization.</p>
</div>
</div>
</div>
</div>
<footer>
<div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
<a href="MarginPercentage.html" class="btn btn-neutral float-right" title="Within Margin Percentage" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right"></span></a>
<a href="MergeMaxDicts.html" class="btn btn-neutral float-left" title="Merging Two Dictionaries" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left"></span> Previous</a>
</div>
<hr/>
<div role="contentinfo">
<p>
© Copyright 2019, Ryan Soklaski
</p>
</div>
Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>.
</footer>
</div>
</div>
</section>
</div>
<script type="text/javascript">
jQuery(function () {
SphinxRtdTheme.Navigation.enable(true);
});
</script>
</body>
</html>