【LeetCode】1003. Check If Word Is Valid After Substitutions 解题报告(Python)
作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/
题目地址:https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/
题目描述
We are given that the string "abc"
is valid.
From any valid string V
, we may split V
into two pieces X
and Y
such that X + Y
(X
concatenated with Y
) is equal to V
. (X
or Y
may be empty.) Then, X + "abc" + Y
is also valid.
If for example S = "abc"
, then examples of valid strings are: "abc", "aabcbc", "abcabc", "abcabcababcc"
. Examples of invalid strings are: "abccba", "ab", "cababc", "bac"
.
Return true
if and only if the given string S
is valid.
Example 1:
Input: "aabcbc"
Output: true
Explanation:
We start with the valid string "abc".
Then we can insert another "abc" between "a" and "bc", resulting in "a" + "abc" + "bc" which is "aabcbc".
Example 2:
Input: "abcabcababcc"
Output: true
Explanation:
"abcabcabc" is valid after consecutive insertings of "abc".
Then we can insert "abc" before the last letter, resulting in "abcabcab" + "abc" + "c" which is "abcabcababcc".
Example 3:
Input: "abccba"
Output: false
Example 4:
Input: "cababc"
Output: false
Note:
1 <= S.length <= 20000
S[i] is 'a', 'b', or 'c'
题目大意
初始只给了一个"abc"
字符串,然后可以在该字符串的任意位置插入一个新的"abc"
字符串,然后继续该操作……这些步骤得到的字符串均为有效字符串。如果经过上面的操作无论如何都不能得到的字符串就是无效字符串。
问一个字符串是不是有效字符串。
解题方法
循环
好久没有做过这么简单的题目了……
如果理解了题意应该明白,每次都去插入一个"abc"
字符串,那么到最后一步一定会有"abc"
。所以我们如果倒着来,每次把"abc"
进行替换成""
,那么一定能回到最初的状态,也就是空字符串。
这个方法唯一不太好的是时间复杂度,判断"abc"是否在S中,需要O(N)的时间复杂度,替换这步的操作应该也是O(N),所以总的时间复杂度是O(N^2)。题目给出的S的长度是20000,为什么没有超时呢?我觉得主要是替换的时候会把大量的"abc"同时替换掉了,这样每次操作就把字符串大幅变短了。
python代码如下:
class Solution(object):
def isValid(self, S):
"""
:type S: str
:rtype: bool
"""
while "abc" in S:
S = S.replace("abc", "")
return not S
日期
2019 年 3 月 3 日 —— 3月开始,春天到了
最新文章
- lower函数
- Attribute在.net编程中的应用
- [SmartFoxServer概述]Zones和Rooms结构
- ecshop的几个小瑕疵
- UVA 10054 The Necklace
- 如何更好地理解和使用Github
- HDU 4793 2013 Changsha Regional Collision[简单的平面几何]
- php 提交表单
- iOS开发frame, contentSize, contentOffset, contentInset 区别联系浅析
- <;C++Primer>;第四版 阅读笔记 第三部分 “类和数据抽象”
- 使用javaAPI操作hdfs
- K相邻算法
- Redis集群教程(Redis cluster tutorial)
- mysql 开启root外部链接权限
- Windows SDK DDK WDK (Windows Driver Kit) 区别
- 最大公约数&;&;最小公倍数
- python内置模块之collections(六)
- emacs编译整个emacs.d目录
- Linux关机和重启命令总结
- django事物回滚
热门文章
- MetaboAnalyst的多组学分析
- c#表格序号列
- Spark基础:(一)初识Spark
- 大数据学习day22------spark05------1. 学科最受欢迎老师解法补充 2. 自定义排序 3. spark任务执行过程 4. SparkTask的分类 5. Task的序列化 6. Task的多线程问题
- 从源码看RequestMappingHandlerMapping的注册与发现
- TCP中的TIME_WAIT状态
- OpenStack之三: 安装MySQL,rabbitmq, memcached
- 【Linux】【Services】【SaaS】Docker+kubernetes(7. 安装Docker私有镜像仓库)
- Flink Exactly-once 实现原理解析
- <;转>;Hadoop入门总结