Amazon Interview - Check string is multiple duplicate - 我的博客 - ITeye技术网站
有一种String,是把一个更短的String重复n次而构成的，那个更短的String长度至少为2，输入一个String写代码返回true或者false
例子：
"abcabcabc" true 因为它把abc重复3次构成
"bcdbcdbcde" false 最后一个是bcde
"abcdabcd" True 因为它是abcd重复2次构成
"xyz" false 因为它不是某一个String重复
"aaaaaaaaaa" false 重复的短String长度应至少为2（这里不能看做aa重复5次)
要求算法复杂度为O(n)
Solution:
patternPos表示从哪里开始匹配。初始值为0。
patternEnd表示模式结束的位置。初始值为0。
当前字符和patternPos不相等的话，说明pattern不成立，patternPos回到开始位置0，patternEnd设为当前字符所在位置i。
当前字符和patternPos相等的话，patternPos加1移到下一个位置，patternEnd保持不变。并检查下如果patternPos超过patternEnd的话，说明截止到当前字符成功匹配，patternPos回到开始开始匹配下一串字符。注意，当i走到最后的话，patternPos就不用清0了。
最后判断成功的条件是，patternPos大于patternEnd的时候，说明整个字符串pattern且至少重复pattern两次。patternEnd大于零，说明pattern长度大于1。
Read full article from Amazon Interview - Check string is multiple duplicate - 我的博客 - ITeye技术网站
No comments:
Post a Comment