内容简介:Given a non-empty string
原题
Given a non-empty string s
, you may delete at most
one character. Judge whether you can make it a palindrome.
Example 1:
<b>Input:</b> "aba" <b>Output:</b> True
Example 2:
<b>Input:</b> "abca" <b>Output:</b> True <b>Explanation:</b> You could delete the character 'c'.
Note:
- The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
思路
水题。
判断是否是回文字符串最简单的方式就是从左右两端逐步向中心逼近(双指针),如下代码:
for (int i = 0; i < s.length(); ++i) { if (s[i] != s[s.length() - 1 - i]) return false; } return true;
题中指出可以最多删除一个字段,那么当遇到左右不一致时会有两个分支产生。即删除左边的字符,或者删除右边的字符。然后分别判断产生的两个子字符串是否是回文字符串即可。
代码
class Solution { public: bool isValid(string s, int start, int end) { for (int i = start; i < (end - start + 1) / 2 + start; ++i) { if (s[i] != s[end - (i - start)]) return false; } return true; } bool validPalindrome(string s) { for (int i = 0; i < s.length() / 2; ++i) { if (s[i] != s[s.length() - i - 1]) { if (!isValid(s, i + 1, s.length() - i - 1) && !isValid(s, i, s.length() - i -2)) return false; break; } } return true; } };
复杂度
时间复杂度:O(n)
空间复杂度:O(n)
技巧
- 由于只有两个分支,所以没有必要利用栈来实现回溯法。
- 再产生两个子字符串时,可以使用两个指针来指定子字符串的范围,而不是使用substr来分隔,并产生一些拷贝。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
统计自然语言处理
宗成庆 / 清华大学出版社 / 2008-5 / 66.00元
内容简介 本书全面介绍了统计自然语言处理的基本概念、理论方法和最新研究进展,内容包括形式语言与自动机及其在自然语言处理中的应用、语言模型、隐马尔可夫模型、语料库技术、汉语自动分词与词性标注、句法分析、词义消歧、统计机器翻译、语音翻译、文本分类、信息检索与问答系统、自动文摘和信息抽取、口语信息处理与人机对话系统等,既有对基础知识和理论模型的介绍,也有对相关问题的研究背景、实现方法和技术现状的详......一起来看看 《统计自然语言处理》 这本书的介绍吧!