文档章节

golang 递归判断回文字符串

guonaihong
 guonaihong
发布于 2015/05/25 22:57
字数 402
阅读 268
收藏 5

判断回文字符串是个比较经典的问题。

思路就是拿第一个字符和最一个字符比较,如果不相同就退出,相同的话继续刚刚的过程,直到第一个字符和最后一个字符相遇或者他们的距离为1时。说明他们是回文字符串。

下面的代码会忽略空白字符 如"1   1  2 1"会认为是回文字符串。

golang

package main

import (
    "fmt"
    "os"
    "strings"
    "unicode/utf8"
)

func doPalindrome(s string) bool {
    if utf8.RuneCountInString(s) <= 1 { 
        return true
    }   

    word := strings.Trim(s, "\t \r\n\v")
    first, sizeOfFirst := utf8.DecodeRuneInString(word)
    last, sizeOfLast := utf8.DecodeLastRuneInString(word)

    if first != last {
        return false
    }   
    return doPalindrome(word[sizeOfFirst : len(word)-sizeOfLast])
}

func IsPalindrome(word string) bool {
    s := ""
    s = strings.Trim(word, "\t \r\n\v")
    if len(s) == 0 || len(s) == 1 { 
        return false
    }   
    return doPalindrome(s)
}

func main() {
    args := os.Args[1:]
    for _, v := range args {
        ok := IsPalindrome(v)
        if ok {
            fmt.Printf("%s\n", v)
        }   
    }   

}


clang  递归版:

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdint.h>

int do_palind(char *first, char *last) {
    /*跳过头部的空白字符*/
    while(*first && isspace(*first)) {
        first++;
    }   
    /*跳过尾部的空白字符*/
    while (first < last && isspace(*last)) {
        last--;
    }   

    if (last - first <= 0)
        return 1;

    if (*first != *last)
        return 0;

    return do_palind(++first, --last);
}

int ispalindrome(const char *str) {
    if (str[0] == '\0' || str[1] == '\0')
        return 0;
    //printf("---->%ld\n", strlen(str));
    return do_palind((char *)str, (char *)str + strlen(str) - 1); 
}

int main(int argc, char **argv) {
    int is; 
    while (*++argv) {
        is = ispalindrome(*argv);
        if (is)
            printf("%s\n", *argv);
    }   
}


clang 循环版:

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int ispalindrome(const char *str) {
    char *last;

    if (str[0] == '\0' || str[1] == '\0')
        return 0;

    last = (char *)str + strlen(str) - 1;

    while (str < last) {
        while (str < last && isspace(*str)) {
            str++;
        }   

        while (str < last && isspace(*last)) {
            last--;
        }   

        if (*str != *last)
            return 0;
        str++;
        last--;
    }   
    return 1;
}

int main(int argc, char **argv) {
    int is; 
    while (*++argv) {
        is = ispalindrome(*argv);
        if (is) {
            printf("%s\n", *argv);
        }   
    }   
}


© 著作权归作者所有

guonaihong

guonaihong

粉丝 6
博文 83
码字总数 27591
作品 1
徐汇
程序员
私信 提问
递归(四)--判断回文字符串--java实现

使用String的API中的charAt(int index)函数来判断两端对称位置上的字符是否相等。 使用递归 递归的结束需要简单情景 1. 字符串长度可能会奇数或偶数: 如果字符串长度是奇数,判断到最后,左...

Amui
2015/10/01
381
0
Leetcode【60、79、93、131、842】

问题描述:【Math】60. Permutation Sequence 解题思路: 这道题是一个从 1 到 n 的数组,共有 n! 个全排列序列,找到第 k 个全排列序列。 刚开始没仔细读题就之间 DFS 回溯,很快写好但超时...

牛奶芝麻
2019/07/09
0
0
计算字符串中回文子串的个数 Palindromic Substrings

问题: Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different ......

叶枫啦啦
2018/01/13
202
0
《程序员代码面试指南》Python实现(个人读书笔记)

说明   最近一直在读左神的书——《程序员代码面试指南—IT名企算法与数据结构题目最优解》,为了记录自己的学习成果,并且方便以后查看,将自己读书时的想法与使用python实现的代码记录在...

qq_34342154
2017/09/09
0
0
前端分享会--从一道算法题目开始的学习

算法题 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 理解 所谓回文,就是字符串反过来或者顺着念都是一样的。这就意味着我们可以通过字符串与反向排序之后...

ziven先生
2019/04/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Kettle自定义jar包供javascript使用

我们都知道 Kettle 是用 Java 语言开发,并且可以在 JavaScript 里面直接调用 java 类方法。所以有些时候,我们可以自定义一些方法,来供 JavaScript 使用。 本篇文章有参考自:https://www...

CREATE_17
昨天
82
0
处理CSV文件中的逗号

我正在寻找有关如何处理正在创建的csv文件的建议,然后由我们的客户上传,并且该值可能带有逗号(例如公司名称)。 我们正在研究的一些想法是:带引号的标识符(值“,”值“,”等)或使用|...

javail
昨天
79
0
如何克隆一个Date对象?

将Date变量分配给另一个变量会将引用复制到同一实例。 这意味着更改一个将更改另一个。 如何实际克隆或复制Date实例? #1楼 简化版: Date.prototype.clone = function () { return new ...

技术盛宴
昨天
73
0
计算一个数的数位之和

计算一个数的数位之和 例如:128 :1+2+8 = 11 public int numSum(int num) { int sum = 0; do { sum += num % 10; } while ((num = num / 10) > 0); return sum;......

SongAlone
昨天
124
0
为什么图片反复压缩后普遍会变绿,而不是其他颜色?

作者:Lion Yang 链接:https://www.zhihu.com/question/29355920/answer/119088684 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 业余版概要:安卓的...

shzwork
昨天
71
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部