<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 0125. 驗證回文串 ## 題目地址(125. 驗證回文串) <https://leetcode-cn.com/problems/valid-palindrome/description/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個字符串,驗證它是否是回文串,只考慮字母和數字字符,可以忽略字母的大小寫。 說明:本題中,我們將空字符串定義為有效的回文串。 示例 1: 輸入: "A man, a plan, a canal: Panama" 輸出: true 示例 2: 輸入: "race a car" 輸出: false ``` ``` ## 前置知識 - 回文 - 雙指針 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 - facebook - microsoft - uber - zenefits ## 思路 這是一道考察回文的題目,而且是最簡單的形式,即判斷一個字符串是否是回文。 針對這個問題,我們可以使用頭尾雙指針, - 如果兩個指針的元素不相同,則直接返回 false, - 如果兩個指針的元素相同,我們同時更新頭尾指針,循環。 直到頭尾指針相遇。 時間復雜度為 O(n). 拿“noon”這樣一個回文串來說,我們的判斷過程是這樣的: ![](https://img.kancloud.cn/a1/82/a1822954562df79143a24c1dbbb4c26b_565x296.jpg) 拿“abaa”這樣一個不是回文的字符串來說,我們的判斷過程是這樣的: ![](https://img.kancloud.cn/bf/e1/bfe17a86374b3b3fe6ac3f559a958c8b_555x286.jpg) ## 關鍵點解析 - 雙指針 ## 代碼 - 語言支持:JS,C++,Python JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=125 lang=javascript * * [125] Valid Palindrome */</span> <span class="hljs-title">// 只處理英文字符(題目忽略大小寫,我們前面全部轉化成了小寫, 因此這里我們只判斷小寫)和數字</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">isValid</span>(<span class="hljs-params">c</span>) </span>{ <span class="hljs-keyword">const</span> charCode = c.charCodeAt(<span class="hljs-params">0</span>); <span class="hljs-keyword">const</span> isDigit = charCode >= <span class="hljs-string">"0"</span>.charCodeAt(<span class="hljs-params">0</span>) && charCode <= <span class="hljs-string">"9"</span>.charCodeAt(<span class="hljs-params">0</span>); <span class="hljs-keyword">const</span> isChar = charCode >= <span class="hljs-string">"a"</span>.charCodeAt(<span class="hljs-params">0</span>) && charCode <= <span class="hljs-string">"z"</span>.charCodeAt(<span class="hljs-params">0</span>); <span class="hljs-keyword">return</span> isDigit || isChar; } <span class="hljs-title">/** * @param {string} s * @return {boolean} */</span> <span class="hljs-keyword">var</span> isPalindrome = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">s</span>) </span>{ s = s.toLowerCase(); <span class="hljs-keyword">let</span> left = <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> right = s.length - <span class="hljs-params">1</span>; <span class="hljs-keyword">while</span> (left < right) { <span class="hljs-keyword">if</span> (!isValid(s[left])) { left++; <span class="hljs-keyword">continue</span>; } <span class="hljs-keyword">if</span> (!isValid(s[right])) { right--; <span class="hljs-keyword">continue</span>; } <span class="hljs-keyword">if</span> (s[left] === s[right]) { left++; right--; } <span class="hljs-keyword">else</span> { <span class="hljs-keyword">break</span>; } } <span class="hljs-keyword">return</span> right <= left; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">isPalindrome</span><span class="hljs-params">(<span class="hljs-params">string</span> s)</span> </span>{ <span class="hljs-keyword">if</span> (s.empty()) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">const</span> <span class="hljs-keyword">char</span>* s1 = s.c_str(); <span class="hljs-keyword">const</span> <span class="hljs-keyword">char</span>* e = s1 + s.length() - <span class="hljs-params">1</span>; <span class="hljs-keyword">while</span> (e > s1) { <span class="hljs-keyword">if</span> (!<span class="hljs-params">isalnum</span>(*s1)) {++s1; <span class="hljs-keyword">continue</span>;} <span class="hljs-keyword">if</span> (!<span class="hljs-params">isalnum</span>(*e)) {--e; <span class="hljs-keyword">continue</span>;} <span class="hljs-keyword">if</span> (<span class="hljs-params">tolower</span>(*s1) != <span class="hljs-params">tolower</span>(*e)) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">else</span> {--e; ++s1;} } <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isPalindrome</span><span class="hljs-params">(self, s: str)</span> -> bool:</span> left, right = <span class="hljs-params">0</span>, len(s) - <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> left < right: <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> s[left].isalnum(): left += <span class="hljs-params">1</span> <span class="hljs-keyword">continue</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> s[right].isalnum(): right -= <span class="hljs-params">1</span> <span class="hljs-keyword">continue</span> <span class="hljs-keyword">if</span> s[left].lower() == s[right].lower(): left += <span class="hljs-params">1</span> right -= <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: <span class="hljs-keyword">break</span> <span class="hljs-keyword">return</span> right <= left <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isPalindrome2</span><span class="hljs-params">(self, s: str)</span> -> bool:</span> <span class="hljs-string">""" 使用語言特性進行求解 """</span> s = <span class="hljs-string">''</span>.join(i <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> s <span class="hljs-keyword">if</span> i.isalnum()).lower() <span class="hljs-keyword">return</span> s == s[::<span class="hljs-params">-1</span>] ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(1)O(1)O(1) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看