检测字符串中的重复字符

问题描述 投票:4回答:7

我正在进行《破解编码访谈》一书中的练习,我试图确定字符串中是否有重复的字符。我正在使用ArrayList数据结构。我的方法的返回类型为Boolean,如果存在重复,则返回true;如果没有重复的字符,则返回false。我添加了第三条return语句,以便程序可以编译,但始终返回false。

import java.util.*;

public class QuestionOneCrackingCode {

    public static void main(String[] args) {
        String s = "abcdefga";
        ArrayList<String> c = new ArrayList<String>();
        c.add(s);

        System.out.print(check(c));
    }

    public static boolean check(ArrayList<String> g) {
        for (int i = 0; i < g.size(); i++) {
            for (int j = i + 1; j < g.size(); j++) {
                if (g.get(i) == g.get(j)) {
                    return true;
                } else {
                    return false;
                }
            }
        }
        return false;
    }
}
java string arraylist char
7个回答
4
投票

您没有将字符串分成字符,而是创建了一个包含字符串的单元素列表。无需对算法做大的改动,就可以这样:

public static void main(String[] args) {
    String s = "abcdefga";

    System.out.print(check(s));
}

public static boolean check(CharSequence g) {
    for (int i = 0; i < g.length(); i++) {
        for (int j = i + 1; j < g.length(); j++) {
            if (g.charAt(i) == g.charAt(j)) {
                return true;
            }
        }
    }
    return false;
}

请注意,第一个return false;也是不正确的,因为它将阻止算法继续通过第一个比较。

顺便说一句,are比较字符串时,应使用.equals()而不是==


2
投票

您的解决方案比较列表中的字符串引用。列表本身仅包含一个字符串。

尝试以下操作:

// check one string for duplicate chars
public static boolean check(String checkString)
{
    // result flag
    boolean foundDuplicate = false;
    // get string length
    int stringLength = checkString.length();
    // create a set for all found characters (max size is number
    // of characters in the string to check
    Set<Character> characters = new HashSet<>(stringLength);
    // loop all characters in string
    for (int i = 0; i < stringLength; i++)
    {
        // construct a object (may be use internal JDK cache)
        Character c = Character.valueOf(checkString.charAt(i));
        // check if character is already found
        if (characters.contains(c))
        {
            // yes, set result to TRUE
            foundDuplicate = true;
            // break the loop
            break;
        }
        else
        {
            // not found, add char to set
            characters.add(c);
        }
    }
    return foundDuplicate;
}

这受字符串长度和堆大小的限制。但是我认为所有UTF-8字符都可以放入堆中。

@@ Maarten Bodewes,您是对的。该检查可以简化为:

        // add character to set and check result
        if (!characters.add(c))
        {
            // returned false: character already exists
            foundDuplicate = true;
            // break the loop
            break;
        }
        // no else necessary

1
投票

这是我的代码版本的结果。

abcdefga true
abcdefgh false
abcdefdh true
  1. 我修改了check参数以采用单个String。不需要字符串列表。

  2. 在检查方法中,一旦一对字符匹配,您可以退出。您必须先测试整个字符串,然后才能说没有匹配的字符。

  3. 第一个for循环可以停在倒数第二个字符处。第二个for循环将获取最后一个字符。

  4. 因为我正在比较char值,所以我使用==。如果我在比较String值,则将使用.equals方法。

这里是代码。

package com.ggl.testing;

public class QuestionOneCrackingCode {

    public static void main(String[] args) {
        String s = "abcdefga";
        System.out.println(s + " " + check(s));
        s = "abcdefgh";
        System.out.println(s + " " + check(s));
        s = "abcdefdh";
        System.out.println(s + " " + check(s));
    }

    public static boolean check(String s) {
        for (int i = 0; i < (s.length() - 1); i++) {
            for (int j = i + 1; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    return true;
                }
            }
        }
        return false;
    }
}

1
投票

我的参与:

    public static void main(String[] args) {
        System.out.println(check("abcdefga"));                    // true
        System.out.println(check("noduplicate"));                 // false
        System.out.println(check("withduplicate"));               // true
        System.out.println(check("abcdefghijklmnopqrstuvwxyz"));  // false
        System.out.println(check("abcdefghijklmnopqrstuvwxyzz")); // true
    }

    /**@brief Check if a String contains duplicated characters.
     * Strong expectation for the string: The String must only contains
     * lowercase alpha characters (ie. in [a-z])
     * @returns true if a char is present more than once */
    public static boolean check(String str) {
        int presentChars = 0; // will store the table of already found characters
        int l = str.length();
        for (int i = 0; i < l; ++i) {
            char c = str.charAt(i);
            int offset = c - 'a';             // a=0, b=1, ... z=25
            int mask = 1 << offset;
            if ((presentChars& mask) != 0) {  // Oh! Char already tagged as found
                return true;                  // No need to process further, bye!
            }
            presentChars|= mask;              // Tag the current char as present
        }
        return false;                         // No duplicate
    }

}

我使用此代码的目标是最大程度地减少复杂性。在最坏的情况下,该算法位于O(N)中。另外,该函数的内存占用非常低:即使我为了提高可读性而使用更多int,实际上仅需要一个presentChars =)

此代码的缺点:输入的字符串有很大的先决条件。我已经在评论中对此进行了详细说明,但它仅适用于[a-z]范围内的字符。

希望对您有所帮助!


0
投票

在Java 8中,您可以这样操作:

public static boolean check(CharSequence checkString)
{
  return checkString.length() != checkString.chars().distinct().count();
}

即如果字符串中不同字符的数量与字符总数不同,则说明存在重复。这不一定是最有效的方法,但是它是简洁的。


0
投票
  1. 使用字符串而不是ArrayList。
  2. 如果比较失败,请不要返回,您需要继续搜索并且不要返回false,这就是为什么它总是返回false的原因。
  3. 即使这不是最优化的解决方案,也请尝试考虑存储桶排序及其如何解决此问题。这将使您的解决方案在O(N)而不是O(N ^ 2)中运行。
public static boolean check(String g) {

    for (int i = 0; i < g.length(); i++) {
        for (int j = i + 1; j < g.length(); j++) {
            if (g.charAt(i) == (g.charAt(j))) {
                return true;
            }
        }
    }

    return false;
}

0
投票

[我使用一个表格来计算一个字符重复多少次,如果一个字符出现多次,然后返回true,则最坏情况下的代码为O(n)

public static void main(String[] args) {

    String test ="abdefghijklmnoPQRSTUVWXYZa";
    System.out.println(isThereAnyCharacterRepeated(test));
}


public static boolean isThereAnyCharacterRepeated(String str){

    int repeatedCharacters[] = new int[255];
    for(int i=0;i<str.length();i++){
        int index=(int)str.charAt(i);
        repeatedTable[index]++;
        if(repeatedTable[index]>1)return true;
    }
    return false;
}
© www.soinside.com 2019 - 2024. All rights reserved.