acgo题库
  • 首页
  • 题库
  • 题单
  • 竞赛
  • 讨论
  • 排行
  • 团队
  • 备赛专区

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
登录
注册
题目详情题解(0)讨论(0)提交记录(0)
  • 官方题解|替换子串使两串相等

    题目解析 两种操作本质上就是可以把 sss 中的 'a' 向右移动,'c' 向左移动。 所以把 sss 和 ttt 中的所有字符 'b' 去掉之后,两个字符串应该是相同的。 另外,由于 'a' 不能向左移动,'c' 不能向右移动,所以要检查字符串 sss 和 ttt 中,对应的字符 'a' 和字符 'b' 的下标。 对于字符 'a',在 sss 中每个字符 'a' 在字符串 ttt 中都应该 有一个下标大于等于 它的 'a' 与之对应; 相对对应的,在 sss 中每个字符 'c' 在字符串 ttt 中都应该 有一个下标小于等于 它的 'c' 与之对应。 AC代码 复杂度分析 检查 sss 和 ttt 去掉所有字符 'b' 之后是否相等时间复杂度为 O(n)O(n)O(n)。 检查 sss 中字符 'a' 和 'b' 相对于在字符串 ttt 中的位置时间复杂度为 O(n)O(n)O(n)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    userId_undefined

    AC君

    管理员
    倔强青铜
    21阅读
    0回复
    1点赞
首页