目录
字符串解码
方法一:栈(Java)
方法二:递归(Go)
首页 Java java教程 如何使用Go Java算法进行字符串解码?

如何使用Go Java算法进行字符串解码?

Apr 25, 2023 pm 11:52 PM
java go

字符串解码

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

  • 示例 1:

输入:s = "3[a]2[bc]"

输出:"aaabcbc"

  • 示例 2:

输入:s = "3[a2[c]]"

输出:"accaccacc"

  • 示例 3:

输入:s = "2[abc]3[cd]ef"

输出:"abcabccdcdcdef"

  • 示例 4:

输入:s = "abc3[cd]xyz"

输出:"abccdcdcdxyz"

方法一:栈(Java)

看到括号的匹配,首先应该想到的就是用栈来解决问题。

首先因为数字可能不止一位,为了更清晰方便可以使用两个栈,一个存储数字,一个存字符。当遇到除了]外的字符先入字符栈,遇到数字则将完整的数字转换后入数字栈,而当遇到]时将字符栈中弹出直到[为止的字符构成一个临时字符串,并弹出数字栈顶元素,将临时字符串重复该数字次数后重新入字符栈。

当从左到右遍历完原始串后栈中元素就是最后的答案

具体方法思路:遍历这个栈

  • 如果当前的字符为数位,解析出一个数字(连续的多个数位)并进栈

  • 如果当前的字符为字母或者左括号,直接进栈

  • 如果当前的字符为右括号,开始出栈,一直到左括号出栈,出栈序列反转后拼接成一个字符串,此时取出栈顶的数字,就是这个字符串应该出现的次数,我们根据这个次数和字符串构造出新的字符串并进栈

class Solution {
    int ptr;
    public String decodeString(String s) {
        LinkedList<String> stk = new LinkedList<String>();
        ptr = 0;
        while (ptr < s.length()) {
            char cur = s.charAt(ptr);
            if (Character.isDigit(cur)) {
                // 获取一个数字并进栈
                String digits = getDigits(s);
                stk.addLast(digits);
            } else if (Character.isLetter(cur) || cur == &#39;[&#39;) {
                // 获取一个字母并进栈
                stk.addLast(String.valueOf(s.charAt(ptr++))); 
            } else {
                ++ptr;
                LinkedList<String> sub = new LinkedList<String>();
                while (!"[".equals(stk.peekLast())) {
                    sub.addLast(stk.removeLast());
                }
                Collections.reverse(sub);
                // 左括号出栈
                stk.removeLast();
                // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                int repTime = Integer.parseInt(stk.removeLast());
                StringBuffer t = new StringBuffer();
                String o = getString(sub);
                // 构造字符串
                while (repTime-- > 0) {
                    t.append(o);
                }
                // 将构造好的字符串入栈
                stk.addLast(t.toString());
            }
        }
        return getString(stk);
    }
    public String getDigits(String s) {
        StringBuffer ret = new StringBuffer();
        while (Character.isDigit(s.charAt(ptr))) {
            ret.append(s.charAt(ptr++));
        }
        return ret.toString();
    }
    public String getString(LinkedList<String> v) {
        StringBuffer ret = new StringBuffer();
        for (String s : v) {
            ret.append(s);
        }
        return ret.toString();
    }
}
登录后复制

时间复杂度:O(N)

空间复杂度:O(N)

方法二:递归(Go)

上文提到的方法为使用栈,因此我们可以随之想到通过使用递归的方式来完成。具体递归的思路,请看下文内容。

需要解决多个括号之间的嵌套问题。也就是重叠子问题。使用栈或递归的解题方式都是可以。

  • 1、首先标识右括号结束的位置。

  • 2、遇到左括号,i+1传递给下一次

  • 3、结束左括号的运行将乘积次数置零,i=上一次右括号接触的位置。继续将右括号外面剩余的字符加完。

具体思路:从左向右解析字符串:

  • 如果当前位置为数字位,那么后面一定包含一个用方括号表示的字符串,即属于这种情况:k[...]:

  • 我们可以先解析出一个数字,然后解析到了左括号,递归向下解析后面的内容,遇到对应的右括号就返回,此时我们可以根据解析出的数字 x 解析出的括号里的字符串 s' 构造出一个新的字符串 X * s′

  • 我们把 k[...] 解析结束后,再次调用递归函数,解析右括号右边的内容

  • 如果当前位置是字母位,那么我们直接解析当前这个字母,然后递归向下解析这个字母后面的内容。

func decodeString(s string) string {
	var decode func(start int) (string, int)
	decode = func(start int) (str string, end int) {
		num:= 0
		for i := start; i < len(s); i++ {
			if isNumber(s[i]) {
				num = num*10 + int(s[i]-&#39;0&#39;)
			} else if isLetter(s[i]) {
				str += string(s[i])
			} else if s[i] == &#39;[&#39; {
				item, index := decode(i + 1)
				for num != 0 {
					str += item
					num--
				}
				i = index
			} else if s[i] == &#39;]&#39; {
				end = i
				break
			}
		}
		return str, end
	}
	res, _ := decode(0)
	return res
}
func isLetter(u uint8) bool {
	return u >= &#39;A&#39; && u <= &#39;Z&#39; || u >= &#39;a&#39; && u <= &#39;z&#39;
}
func isNumber(u uint8) bool {
	return u >= &#39;0&#39; && u <= &#39;9&#39;
}
登录后复制

时间复杂度:O(N)

空间复杂度:O(N)

以上是如何使用Go Java算法进行字符串解码?的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

Java 中的平方根 Java 中的平方根 Aug 30, 2024 pm 04:26 PM

Java 中的平方根指南。下面我们分别通过例子和代码实现来讨论平方根在Java中的工作原理。

Java 中的完美数 Java 中的完美数 Aug 30, 2024 pm 04:28 PM

Java 完美数指南。这里我们讨论定义,如何在 Java 中检查完美数?,示例和代码实现。

Java 中的随机数生成器 Java 中的随机数生成器 Aug 30, 2024 pm 04:27 PM

Java 随机数生成器指南。在这里,我们通过示例讨论 Java 中的函数,并通过示例讨论两个不同的生成器。

Java中的Weka Java中的Weka Aug 30, 2024 pm 04:28 PM

Java 版 Weka 指南。这里我们通过示例讨论简介、如何使用weka java、平台类型和优点。

Java 中的阿姆斯特朗数 Java 中的阿姆斯特朗数 Aug 30, 2024 pm 04:26 PM

Java 中的阿姆斯特朗数指南。这里我们讨论一下java中阿姆斯特朗数的介绍以及一些代码。

Java 中的史密斯数 Java 中的史密斯数 Aug 30, 2024 pm 04:28 PM

Java 史密斯数指南。这里我们讨论定义,如何在Java中检查史密斯号?带有代码实现的示例。

Java Spring 面试题 Java Spring 面试题 Aug 30, 2024 pm 04:29 PM

在本文中,我们保留了最常被问到的 Java Spring 面试问题及其详细答案。这样你就可以顺利通过面试。

突破或从Java 8流返回? 突破或从Java 8流返回? Feb 07, 2025 pm 12:09 PM

Java 8引入了Stream API,提供了一种强大且表达力丰富的处理数据集合的方式。然而,使用Stream时,一个常见问题是:如何从forEach操作中中断或返回? 传统循环允许提前中断或返回,但Stream的forEach方法并不直接支持这种方式。本文将解释原因,并探讨在Stream处理系统中实现提前终止的替代方法。 延伸阅读: Java Stream API改进 理解Stream forEach forEach方法是一个终端操作,它对Stream中的每个元素执行一个操作。它的设计意图是处

See all articles