字符串的排列

[编程题]字符串的排列

热度指数：5392 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母,例如ac

输出描述:

[ac, ca]

示例1

输入

acc

输出

[acc, cac, cca]

算法知识视频讲解

江月何年初

package main

import (
    "fmt"
    "sort"
)

func main() {
    var s string
    fmt.Scan(&s)
    
    res := []string{}
    n := len(s)
    st := make([]bool,n)
    visited := make(map[string]bool)

    dfs(s,"",&st,&res,&visited)
    sort.Strings(res)
    for i:=0;i<len(res)-1;i++{
        res[i] = res[i]+","
    }
    fmt.Println(res)
}

func dfs(s string,tmp string,st *[]bool,res *[]string,visited *map[string]bool){
    if (*visited)[tmp]{
        return
    }else{
        (*visited)[tmp] = true
    }
    if len(tmp) == len(s){
        (*res) = append((*res), tmp) 
        return 
    }
    for i:=0 ; i < len(s);i++{
        if !(*st)[i]{
            (*st)[i] = true
            dfs(s,tmp + string(s[i]),st,res,visited)
            (*st)[i] = false
        }
    }
}

发表于 2024-09-05 09:27:52 回复(0)

牛客887434717号

package main

import (
	"fmt"
	"sort"
)

func main() {
	var s string
	fmt.Scan(&s)
	res := calStr(s)

	sort.Slice(res, func(i, j int) bool {
		return res[i]+res[j] < res[j]+res[i]
	})

	for i := 0; i < len(res)-1; i++ {
		res[i] += ","
	}
	fmt.Println(res)
}

func calStr(s string) []string {
	res := make([]string, 0)
	m := make(map[string]bool)
	r := []rune(s)
	length := len(r)

	for i := 0; i < length; i++ {
		if length == 2 {
			res = append(res, s)
			r[0], r[1] = r[1], r[0]
			if !m[string(r)] {
				res = append(res, string(r))
				m[string(r)] = true
			}
			break
		} else {
			t := string(r[1:length])
			tmp := calStr(t)
			for _, v := range tmp {
				if !m[string(r[0])+v] {
					res = append(res, string(r[0])+v)
					m[string(r[0])+v] = true
				}
			}
			if i < length-1 {
				r[0], r[i+1] = r[i+1], r[0]
			}
		}
	}
	return res
}

发表于 2024-08-11 18:12:37 回复(0)